Largest planar graphs of diameter $3$ and fixed maximum degree -- connection with fractional matchings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908465457266688 |
|---|---|
| author | Dailly, Antoine Darmon, Sasha Giocanti, Ugo Hilaire, Claire Valicov, Petru |
| author_facet | Dailly, Antoine Darmon, Sasha Giocanti, Ugo Hilaire, Claire Valicov, Petru |
| contents | The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree $Δ$ and diameter $D$. In this paper, we focus on planar graphs of diameter $3$. Fellows, Hell and Seyffarth (1995) proved that for all $Δ\geq 8$, the maximum number $\mathrm{np}_{Δ, D}$ of vertices of a planar graph with maximum degree at most $Δ$ and diameter at most 3 satisfies $\frac{9}{2}Δ- 3 \leq \mathrm{np}_{Δ,3} \leq 8 Δ+ 12$. We show that the lower bound they gave is optimal, up to an additive constant, by proving that there exists $c>0$ such that $\mathrm{np}_{Δ,3} \leq \frac{9}{2}Δ+ c$ for every $Δ\geq 0$. Our proof consists in a reduction to the fractional maximum matching problem on a specific class of planar graphs, for which we show that the optimal solution is $\tfrac{9}{2}$, and characterize all graphs attaining this bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_18797 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Largest planar graphs of diameter $3$ and fixed maximum degree -- connection with fractional matchings Dailly, Antoine Darmon, Sasha Giocanti, Ugo Hilaire, Claire Valicov, Petru Combinatorics Discrete Mathematics The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree $Δ$ and diameter $D$. In this paper, we focus on planar graphs of diameter $3$. Fellows, Hell and Seyffarth (1995) proved that for all $Δ\geq 8$, the maximum number $\mathrm{np}_{Δ, D}$ of vertices of a planar graph with maximum degree at most $Δ$ and diameter at most 3 satisfies $\frac{9}{2}Δ- 3 \leq \mathrm{np}_{Δ,3} \leq 8 Δ+ 12$. We show that the lower bound they gave is optimal, up to an additive constant, by proving that there exists $c>0$ such that $\mathrm{np}_{Δ,3} \leq \frac{9}{2}Δ+ c$ for every $Δ\geq 0$. Our proof consists in a reduction to the fractional maximum matching problem on a specific class of planar graphs, for which we show that the optimal solution is $\tfrac{9}{2}$, and characterize all graphs attaining this bound. |
| title | Largest planar graphs of diameter $3$ and fixed maximum degree -- connection with fractional matchings |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2507.18797 |