Analogues of Bermond-Bollobás conjecture for cages yield expander families
Abstract
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 for all k ≥ 3 the existence of k-regular expander graphs with Cheeger constant asymptotically bounded below by 1/(k-1) (expander families); thereby establishing a connection between Cages and Expander Graphs.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.9
References
N. Alon, "Eigenvalues and expanders," Combinatorica, vol. 6, no. 2, pp. 83–96, 1986.
J. C. Bermond and B. Bollobás, "The diameter of graphs: A survey," Congressus Numerantium, vol. 32, pp. 3–27, 1981.
N. L. Biggs, "Excess in vertex-transitive graphs," Bulletin of the London Mathematical Society, vol. 14, pp. 52–54, 1982.
N. L. Biggs, "Graphs with large girth," Ars Combinatoria, vol. 25C, pp. 73–80, 1988.
N. L. Biggs, "Constructions for cubic graphs of large girth," Electronic Journal of Combinatorics, vol. 5, 1998.
P. Erdős and H. Sachs, "Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl," Wissenschaftliche Zeitschrift der Universität Halle (Mathematisch-Naturwissenschaftliche Reihe), vol. 12, pp. 251–257, 1963.
G. Exoo and R. Jajcay, "Dynamic cage survey," Electronic Journal of Combinatorics, Dynamic Survey, vol. 16, 2013.
S. Filipovski and R. Jajcay, "A connection between a question of Bermond and Bollobás and Ramanujan graphs," Acta Applicandae Mathematicae, vol. 175, no. 1, pp. 1–10, 2021.
J. Friedman, "A proof of Alon's second eigenvalue conjecture and related problems," Memoirs of the American Mathematical Society, vol. 195, no. 910, 2008.
A. J. Hoffman and R. R. Singleton, "On Moore graphs with diameters 2 and 3," IBM Journal of Research and Development, vol. 4, pp. 497–504, 1960.
F. Lazebnik, S. Sun, and Y. Wang, "Some families of graphs, hypergraphs and digraphs defined by systems of equations: a survey," in D. Labbate (ed.), Selected topics in graph theory and its applications, Lecture Notes of Seminario Interdisciplinare di Matematica, vol. 14, pp. 105–142, 2017.
S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," Bulletin of the American Mathematical Society, New Series, vol. 43, no. 4, pp. 439–561, 2006.
A. Lubotzky, R. Phillips, and P. Sarnak, "Ramanujan graphs," Combinatorica, vol. 8, no. 3, pp. 261–277, 1988.
A. W. Marcus, D. A. Spielman, and N. Srivastava, "Interlacing families I: Bipartite Ramanujan graphs of all degrees," Annals of Mathematics (2), vol. 182, no. 1, pp. 307–325, 2015.
G. A. Margulis, "Explicit constructions of concentrators," Problemy Peredachi Informatsii, vol. 9, no. 4, pp. 71–80, 1973.
M. Miller and J. Širáň, "Moore graphs and beyond: A survey of the degree/diameter problem," Electronic Journal of Combinatorics, Dynamic Survey, vol. 14, 2005.
M. Morgenstern, "Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q," Journal of Combinatorial Theory Series B, vol. 62, no. 1, pp. 44–62, 1994.
J. Y. Yang and J. H. Koolen, "On the order of regular graphs with fixed second largest eigenvalue," Linear Algebra and its Applications, vol. 610, pp. 29–39, 2021.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.