The degree-diameter problem for plane graphs with pentagonal faces
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913202343772160 |
|---|---|
| author | Preez, Brandon Du |
| author_facet | Preez, Brandon Du |
| contents | The degree-diameter problem consists of finding the maximum number of vertices $n$ of a graph with diameter $d$ and maximum degree $Δ$. This problem is well studied, and has been solved for plane graphs of low diameter in which every face is bounded by a 3-cycle (triangulations), and plane graphs in which every face is bounded by a 4-cycle (quadrangulations). In this paper, we solve the degree diameter problem for plane graphs of diameter 3 in which every face is bounded by a 5-cycle (pentagulations). We prove that if $Δ\geq 8$, then $n \leq 3Δ- 1$ for such graphs. This bound is sharp for $Δ$ odd. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11187 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The degree-diameter problem for plane graphs with pentagonal faces Preez, Brandon Du Combinatorics Discrete Mathematics 05C12 (Primary) 05C10, 05C35 (Secondary) The degree-diameter problem consists of finding the maximum number of vertices $n$ of a graph with diameter $d$ and maximum degree $Δ$. This problem is well studied, and has been solved for plane graphs of low diameter in which every face is bounded by a 3-cycle (triangulations), and plane graphs in which every face is bounded by a 4-cycle (quadrangulations). In this paper, we solve the degree diameter problem for plane graphs of diameter 3 in which every face is bounded by a 5-cycle (pentagulations). We prove that if $Δ\geq 8$, then $n \leq 3Δ- 1$ for such graphs. This bound is sharp for $Δ$ odd. |
| title | The degree-diameter problem for plane graphs with pentagonal faces |
| topic | Combinatorics Discrete Mathematics 05C12 (Primary) 05C10, 05C35 (Secondary) |
| url | https://arxiv.org/abs/2401.11187 |