Diameter of Ramanujan Graphs and Random Cayley Graphs
Diameter of Ramanujan Graphs and Random Cayley Graphs
复制标题
拉马努金图和随机凯莱图的直径
DOI：
10.1007/s00493-017-3605-0
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Naser T. Sardari
中科院分区：
文献类型：
--
作者：
Naser T. Sardari
研究了LPS Ramanujan图Xp，q的直径.证明了二部Ramanujan图的直径大于（4/3）logp（n）+O（1），其中n是Xp，q的顶点数.我们还构造了一类（p+1）-正则LPS Ramanujan图Xp，m，使得这些图的直径大于或等于.另一方面，对于任何k-正则Ramanujan图，我们证明了所有顶点对中只有很小一部分的距离大于（1+ n）logk-1（n）。我们还对LPS Ramanujan图和随机Cayley图进行了一些数值实验，结果表明它们的直径分别是渐近的（4/3）logk-1（n）和logk-1（n）.
We study the diameter of LPS Ramanujan graphs Xp,q. We show that the diameter of the bipartite Ramanujan graphs is greater than (4/3)logp(n)+O(1), where n is the number of vertices of Xp,q. We also construct an infinite family of (p+1)-regular LPS Ramanujan graphs Xp,m such that the diameter of these graphs is greater than or equal to ⌊(4/3)logp(n)⌋. On the other hand, for any k-regular Ramanujan graph we show that only a tiny fraction of all pairs of vertices have distance greater than (1+ϵ) logk–1(n). We also have some numerical experiments for LPS Ramanujan graphs and random Cayley graphs which suggest that the diameters are asymptotically (4/3)logk–1(n) and logk–1(n), respectively.