A connection between a question of Bermond and Bollobás and Ramanujan graphs

DOI10.1007/S10440-021-00429-YMaRDI QIDQ2230812zbMATH OpenOpenAlexFDO

Authors Slobodan Filipovski, Robert Jajcay

Publication date 28 September 2021

Published in Acta Applicandae Mathematicae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.07501

zbMATH Keywords

cageMoore boundRamanujan graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Let $n(k,d)$ be the order of the largest undirected graphs of maximum degree $k$ and diameter $d$, and let $M(k,d)$ be the corresponding Moore bound. In this paper, we give a positive answer to the question of Bermond and Bollob'as concerning the Degree/Diameter Problem: Given a positive integer $c>0$, does there exist a pair $k$ and $d$, such that $n(k,d)leqM(k,d)-c?$

Recommendations

• scientific article; zbMATH DE number 1182557
• scientific article; zbMATH DE number 1376670
• Ramanujan graphs
• Note on the girth of Ramanujan graphs
• Ramanujan graphs and exponential sums over function fields

Cites work

• Algebraic Graph Theory
• Dynamic cage survey
• Eigenvalues and expanders
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit constructions of graphs without short cycles and low density codes
• Girth, valency, and excess
• scientific article; zbMATH DE number 3525170 (Why is no real title available?)
• scientific article; zbMATH DE number 2042680 (Why is no real title available?)
• scientific article; zbMATH DE number 3794103 (Why is no real title available?)
• scientific article; zbMATH DE number 7378741 (Why is no real title available?)
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Moore graphs and beyond: a survey of the degree/diameter problem
• On Minimal graphs of maximum even girth
• On the defect of vertex-transitive graphs of given degree and diameter
• On the second eigenvalue of a graph
• Ramanujan graphs
• Spectra of regular graphs and hypergraphs and orthogonal polynomials
• The nonexistence of certain generalized polygons
• The second eigenvalue of regular graphs of given girth

Cited in

(4)

• Energy of strong double graphs
• Approximate Moore graphs are good expanders
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Analogues of Bermond-Bollobás conjecture for cages yield expander families

This page was built for publication: A connection between a question of Bermond and Bollobás and Ramanujan graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230812)