A Connection Between a Question of Bermond and Bollobás and Ramanujan Graphs
2021
If we let $n(k, d)$
denote the order of the largest undirected graphs of maximum degree $k$
and diameter $d$
, and let $M(k,d)$
denote the corresponding Moore bound, then $n(k,d) \leq M(k,d)$
, for all $k \geq 3$
, $d \geq 2 $
. While the inequality has been proved strict for all but very few pairs $k$
and $d$
, the exact relation between the values $n(k,d)$
and $M(k,d)$
is unknown, and the uncertainty of the situation is captured by an open question of Bermond and Bollobas who asked whether it is true that for any positive integer $c>0$
there exist a pair $k$
and $d$
, such that $n(k, d)\leq M(k,d)-c$
. We present a connection of this question to the value $2\sqrt{k-1}$
, which is also essential in the definition of the Ramanujan graphs defined as $k$
-regular graphs whose second largest eigenvalue (in modulus) does not exceed $2 \sqrt{k-1}$
. We further reinforce this surprising connection by showing that if the answer to the question of Bermond and Bollobas were negative and there existed a $c > 0$
such that $n(k,d) \geq M(k,d) - c $
, for all $k \geq 3$
, $d \geq 2 $
, then, for any fixed $k$
and all sufficiently large even $d$
’s, the largest undirected graphs of degree $k$
and diameter $d$
would have to be Ramanujan graphs. This would imply a positive answer to the open question whether infinitely many non-bipartite $k$
-regular Ramanujan graphs exist for any degree $k$
.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
0
Citations
NaN
KQI