A non-existence result for vertex-girth-regular graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910160376561664 |
|---|---|
| author | Jooken, Jorik Lohvynov, Denys |
| author_facet | Jooken, Jorik Lohvynov, Denys |
| contents | A $k$-regular graph of girth $g$ is called vertex-girth-regular if every vertex is contained in the same number of cycles of length $g$. For integers $n, k, g$ and $λ$, we denote such a graph on $n$ vertices in which every vertex lies on exactly $λ$ cycles of length $g$ by a $\text{vgr}(n,k,g,λ)$-graph. It is well-known that any vertex-girth-regular graph satisfies $λ\le \frac{k(k-1)^{\left\lfloor \frac{g}{2} \right\rfloor}}{2}$. Graphs for which $λ$ is close to this bound are of particular interest in connection with the cage problem, since requiring many girth cycles through every vertex is a natural way to isolate highly structured candidates for small regular graphs of prescribed girth. In this paper, we prove that for every $k\ge 3$ and every integer $0< \varepsilon \leq \frac{k-1}{2}$, there does not exist a $\text{vgr}(n,k,5,\frac{k(k-1)^2}{2}-\varepsilon)$-graph. Previous non-existence results had already settled all odd girths at least $7$ and very recently also girth $3$, leaving girth $5$ as the only girth for which no non-trivial non-existence result was known. Thus, our result resolves the final remaining case and completes the picture for odd girths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21486 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A non-existence result for vertex-girth-regular graphs Jooken, Jorik Lohvynov, Denys Combinatorics A $k$-regular graph of girth $g$ is called vertex-girth-regular if every vertex is contained in the same number of cycles of length $g$. For integers $n, k, g$ and $λ$, we denote such a graph on $n$ vertices in which every vertex lies on exactly $λ$ cycles of length $g$ by a $\text{vgr}(n,k,g,λ)$-graph. It is well-known that any vertex-girth-regular graph satisfies $λ\le \frac{k(k-1)^{\left\lfloor \frac{g}{2} \right\rfloor}}{2}$. Graphs for which $λ$ is close to this bound are of particular interest in connection with the cage problem, since requiring many girth cycles through every vertex is a natural way to isolate highly structured candidates for small regular graphs of prescribed girth. In this paper, we prove that for every $k\ge 3$ and every integer $0< \varepsilon \leq \frac{k-1}{2}$, there does not exist a $\text{vgr}(n,k,5,\frac{k(k-1)^2}{2}-\varepsilon)$-graph. Previous non-existence results had already settled all odd girths at least $7$ and very recently also girth $3$, leaving girth $5$ as the only girth for which no non-trivial non-existence result was known. Thus, our result resolves the final remaining case and completes the picture for odd girths. |
| title | A non-existence result for vertex-girth-regular graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.21486 |