A note on girth-diameter cages
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913213113696256 |
|---|---|
| author | Araujo-Pardo, Gabriela Conder, Marston García-Colín, Natalia Kiss, György Leemans, Dimitri |
| author_facet | Araujo-Pardo, Gabriela Conder, Marston García-Colín, Natalia Kiss, György Leemans, Dimitri |
| contents | In this paper, we introduce a problem closely related to the Cage Problem and the Degree Diameter Problem. For integers $k\geq 2$, $g\geq 3$ and $d\geq 1$, we define a $(k;\, g,d)$-graph to be a $k$-regular graph with girth $g$ and diameter $d$. We denote by $n_0(k;\,g,d)$ the smallest possible order of such a graph, and, if such a graph exists, we call it a $(k;g,d)$-cage. In particular, we focus on $(k;\,5,4)$-graphs. We show that $n_0(k;\,5,4) \geq k^2+k+2$ for all $k$, and report on the determination of all $(k;\,5,4)$-cages for $k=3, 4$ and $5$ and examples with $k = 6$, and describe some examples of $(k;\,5,4)$-graphs which prove that $n_0(k;\,5,4) \leq 2k^2$ for infinitely many values of $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15539 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on girth-diameter cages Araujo-Pardo, Gabriela Conder, Marston García-Colín, Natalia Kiss, György Leemans, Dimitri Combinatorics 05C35, 51E15 In this paper, we introduce a problem closely related to the Cage Problem and the Degree Diameter Problem. For integers $k\geq 2$, $g\geq 3$ and $d\geq 1$, we define a $(k;\, g,d)$-graph to be a $k$-regular graph with girth $g$ and diameter $d$. We denote by $n_0(k;\,g,d)$ the smallest possible order of such a graph, and, if such a graph exists, we call it a $(k;g,d)$-cage. In particular, we focus on $(k;\,5,4)$-graphs. We show that $n_0(k;\,5,4) \geq k^2+k+2$ for all $k$, and report on the determination of all $(k;\,5,4)$-cages for $k=3, 4$ and $5$ and examples with $k = 6$, and describe some examples of $(k;\,5,4)$-graphs which prove that $n_0(k;\,5,4) \leq 2k^2$ for infinitely many values of $k$. |
| title | A note on girth-diameter cages |
| topic | Combinatorics 05C35, 51E15 |
| url | https://arxiv.org/abs/2401.15539 |