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.
Fields of Study & Subjects
Mathematics and Applications
Advanced Differential Equations and Dynamical Systems
Mathematical Dynamics and Fractals
Publication details
- Journal / source
- Electronic Journal of Graph Theory and Applications
- Publisher
- The Institute for Research and Community Services (LPPM) ITB
- Volume
- 14
- Issue
- 1
- Pages
- 139–139
- Publication date
- 22 April 2026
- Language
- EN