Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Eze, Leonard Chidiebere
Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava, Slovakia
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Analogues of Bermond-Bollobás conjecture for cages yield expander families Eze, Leonard Chidiebere; Jajcay, Robert
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 14, No 1 (2026): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2026.14.1.9

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.
Co-Authors Jajcay, Robert