Isometric Cycles and a Generalization of Moore Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909255198572544 |
|---|---|
| author | Preez, Brandon Du |
| author_facet | Preez, Brandon Du |
| contents | The equator of a graph is the length of a longest isometric cycle. We bound the order $n$ of a graph from below by its equator $q$, girth $g$ and minimum degree $δ$ - and show that this bound is sharp when there exists a Moore graph with girth $g$ and minimum degree $δ$. The extremal graphs that attain our bound give an analogue of Moore graphs. We prove that these extremal `Moore-like' graphs are regular, and that every one of their vertices is contained in some maximum length isometric cycle. We show that these extremal graphs have a highly structured partition that is unique, and easily derived from any of its maximum length isometric cycles. We characterize the extremal graphs with girth 3 and 4, and those with girth 5 and minimum degree 3. We also bound the order of $C_4$-free graphs with given equator and minimum degree, and show that this bound is nearly sharp. We conclude with some questions and conjectures further relating our extremal graphs to cages and Moore graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10556 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Isometric Cycles and a Generalization of Moore Graphs Preez, Brandon Du Combinatorics Discrete Mathematics 05C12 (Primary) 05C35 (Secondary) The equator of a graph is the length of a longest isometric cycle. We bound the order $n$ of a graph from below by its equator $q$, girth $g$ and minimum degree $δ$ - and show that this bound is sharp when there exists a Moore graph with girth $g$ and minimum degree $δ$. The extremal graphs that attain our bound give an analogue of Moore graphs. We prove that these extremal `Moore-like' graphs are regular, and that every one of their vertices is contained in some maximum length isometric cycle. We show that these extremal graphs have a highly structured partition that is unique, and easily derived from any of its maximum length isometric cycles. We characterize the extremal graphs with girth 3 and 4, and those with girth 5 and minimum degree 3. We also bound the order of $C_4$-free graphs with given equator and minimum degree, and show that this bound is nearly sharp. We conclude with some questions and conjectures further relating our extremal graphs to cages and Moore graphs. |
| title | Isometric Cycles and a Generalization of Moore Graphs |
| topic | Combinatorics Discrete Mathematics 05C12 (Primary) 05C35 (Secondary) |
| url | https://arxiv.org/abs/2407.10556 |