On the Cheeger constant for distance-regular graphs

Abstract

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 $\frac{{\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 imprimitive distance-regular graphs, and most distance-regular graphs with small valency.