On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916370597281792 |
|---|---|
| author | Jajcay, Robert Jooken, Jorik Porupsánszki, István |
| author_facet | Jajcay, Robert Jooken, Jorik Porupsánszki, István |
| contents | A vertex-girth-regular $vgr(v,k,g,λ)$-graph is a $k$-regular graph of girth $g$ and order $v$ in which every vertex belongs to exactly $λ$ cycles of length $g$. While all vertex-transitive graphs are necessarily vertex-girth-regular, the majority of vertex-girth-regular graphs are not vertex-transitive. Similarly, while many of the smallest $k$-regular graphs of girth $g$, the so-called $(k,g)$-cages, are vertex-girth-regular, infinitely many vertex-girth-regular graphs of degree $k$ and girth $g$ exist for many pairs $k,g$. Due to these connections, the study of vertex-girth-regular graphs promises insights into the relations between the classes of extremal, highly symmetric, and locally regular graphs of given degree and girth. This paper lays the foundation to such study by investigating the fundamental properties of $vgr(v,k,g,λ)$-graphs, specifically the relations necessarily satisfied by the parameters $v,k,g$ and $λ$ to admit the existence of a corresponding vertex-girth-regular graph, by presenting constructions of infinite families of $vgr(v,k,g,λ)$-graphs, and by establishing lower bounds on the number $v$ of vertices in a $vgr(v,k,g,λ)$-graph. It also includes computational results determining the orders of smallest cubic and quartic graphs of small girths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14557 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration Jajcay, Robert Jooken, Jorik Porupsánszki, István Combinatorics A vertex-girth-regular $vgr(v,k,g,λ)$-graph is a $k$-regular graph of girth $g$ and order $v$ in which every vertex belongs to exactly $λ$ cycles of length $g$. While all vertex-transitive graphs are necessarily vertex-girth-regular, the majority of vertex-girth-regular graphs are not vertex-transitive. Similarly, while many of the smallest $k$-regular graphs of girth $g$, the so-called $(k,g)$-cages, are vertex-girth-regular, infinitely many vertex-girth-regular graphs of degree $k$ and girth $g$ exist for many pairs $k,g$. Due to these connections, the study of vertex-girth-regular graphs promises insights into the relations between the classes of extremal, highly symmetric, and locally regular graphs of given degree and girth. This paper lays the foundation to such study by investigating the fundamental properties of $vgr(v,k,g,λ)$-graphs, specifically the relations necessarily satisfied by the parameters $v,k,g$ and $λ$ to admit the existence of a corresponding vertex-girth-regular graph, by presenting constructions of infinite families of $vgr(v,k,g,λ)$-graphs, and by establishing lower bounds on the number $v$ of vertices in a $vgr(v,k,g,λ)$-graph. It also includes computational results determining the orders of smallest cubic and quartic graphs of small girths. |
| title | On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.14557 |