## 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 [Formula presented], 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.

Original language | English |
---|---|

Article number | 105227 |

Number of pages | 20 |

Journal | Journal of Combinatorial Theory, Series A |

Volume | 173 |

DOIs | |

Publication status | Published - Jul 2020 |

## Keywords

- Cheeger constant
- Distance-regular graphs
- Isoperimetric constant
- Laplacian eigenvalues
- Spectral graph theory