On the Cheeger constant for distance-regular graphs
On the Cheeger constant for distance-regular graphs
复制标题
关于距离正则图的 Cheeger 常数
DOI：
10.1016/j.jcta.2020.105227
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Greg Markowsky
中科院分区：
文献类型：
--
作者：
Zhi Qiao;Jack Koolen;Greg Markowsky
图的切格常数是子图的大小与其边界的大小之间可能的最小比率。众所周知，这个常数必须至少是λ1 2，其中λ1是拉普拉斯矩阵的最小正特征值。本文的主题是作者的一个猜想，即对于距离正则图，切格常数至多为λ1。特别地，我们证明了已知的无限族距离正则图、直径为2的距离正则图(强正则图)、几类直径为3的距离正则图以及大多数小度距离正则图的猜想。
The Cheeger constant of a graph is the smallest possible ratio between the size of a subgraph and the size of its boundary. It is well known that this constant must be at least λ 1 2, where λ 1 is the smallest positive eigenvalue of the Laplacian matrix. The subject of this paper is a conjecture of the authors that for distance-regular graphs the Cheeger constant is at most λ 1. In particular, we prove the conjecture for the known infinite families of distance-regular graphs, distance-regular graphs of diameter 2 (the strongly regular graphs), several classes of distance-regular graphs with diameter 3, and most distance-regular graphs with small valency.
登录
查看更多内容
DOI：
10.1007/978-1-4613-0163-9
发表时间：
2001-04
期刊：
--
影响因子：
--
作者：
C. D. Godsil;G. Royle
通讯作者：
C. D. Godsil;G. Royle
DOI：
10.1016/s0097-3165(03)00006-2
发表时间：
2003-05
期刊：
J. Comb. Theory A
影响因子：
--
作者：
A. Brouwer;C. Godsil;J. Koolen;W. Martin
通讯作者：
A. Brouwer;C. Godsil;J. Koolen;W. Martin
DOI：
10.1016/j.ejc.2010.05.012
发表时间：
2009-02
期刊：
Eur. J. Comb.
影响因子：
--
作者：
J. Koolen;Jongyook Park
通讯作者：
J. Koolen;Jongyook Park
DOI：
10.1016/j.disc.2013.06.012
发表时间：
2013-10
期刊：
Discret. Math.
影响因子：
--
作者：
G. C. Kim;Yoonjin Lee
通讯作者：
G. C. Kim;Yoonjin Lee
DOI：
10.1007/3-540-48863-4_3
发表时间：
2007
期刊：
--
影响因子：
--
作者：
A. Hora;N. Obata
通讯作者：
A. Hora;N. Obata