Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.06629 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912021142831104 |
|---|---|
| author | Eze, Leonard Chidiebere Jajcay, Robert |
| author_facet | Eze, Leonard Chidiebere Jajcay, Robert |
| contents | This paper presents a possible link between Cages and Expander Graphs by introducing three interconnected variants of the Bermond and Bollobás Conjecture, originally formulated in 1981 within the context of the Degree/Diameter Problem. We adapt these conjectures to cages, with the most robust variant posed as follows: Does there exist a constant $c$ such that for every pair of parameters $(k,g)$ there exists a $k$-regular graph of girth $g$ and order not exceeding $ M(k,g) + c $?; where $M(k,g)$ denotes the value of the so-called Moore bound for cages. We show that a positive answer to any of the three variants of the Bermond and Bollobás Conjecture for cages considered in our paper would yield expander graphs (expander families); thereby establishing a connection between Cages and Expander Graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06629 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Analogues of Bermond-Bollobás Conjecture for Cages Yield Expander Families Eze, Leonard Chidiebere Jajcay, Robert Combinatorics Discrete Mathematics This paper presents a possible link between Cages and Expander Graphs by introducing three interconnected variants of the Bermond and Bollobás Conjecture, originally formulated in 1981 within the context of the Degree/Diameter Problem. We adapt these conjectures to cages, with the most robust variant posed as follows: Does there exist a constant $c$ such that for every pair of parameters $(k,g)$ there exists a $k$-regular graph of girth $g$ and order not exceeding $ M(k,g) + c $?; where $M(k,g)$ denotes the value of the so-called Moore bound for cages. We show that a positive answer to any of the three variants of the Bermond and Bollobás Conjecture for cages considered in our paper would yield expander graphs (expander families); thereby establishing a connection between Cages and Expander Graphs. |
| title | Analogues of Bermond-Bollobás Conjecture for Cages Yield Expander Families |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2409.06629 |