On the Cheeger constant for distance-regular graphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:173

Article

Qiao, Zhi¹  Koolen, Jack H.^2,3  Markowsky, Greg⁴ 

[1] Sichuan Normal Univ, Sch Math Sci, Chengdu, Peoples R China

[2] Chinese Acad Sci, Wen Tsun Wu Key Lab, Hefei, Peoples R China

[3] USTC, Sch Math Sci, Hefei, Peoples R China

[4] Monash Univ, Dept Math, Melbourne, Vic, Australia

关键词: Distance-regular graphs;    Spectral graph theory;    Laplacian eigenvalues;    Cheeger constant;    Isoperimetric constant;   

DOI  :  10.1016/j.jcta.2020.105227

来源: Elsevier

【 摘 要 】

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 lambda 1/2, where lambda(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 lambda(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. (c) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free