An upper bound on the Cheeger constant of a distance-regular graph

Gil Chun Kim, Yoonjin Lee

Research output: Contribution to journalArticlepeer-review

Abstract

We present an upper bound on the Cheeger constant of a distance-regular graph. Recently, the authors found an upper bound on the Cheeger constant of distance-regular graph under a certain restriction in their previous work. Our new bound in the current paper is much better than the previous bound, and it is a general bound with no restriction. We point out that our bound is explicitly computable by using the valencies and the intersection matrix of a distance-regular graph. As a major tool, we use the discrete Green’s function, which is defined as the inverse of β-Laplacian for some positive real number β. We present some examples of distance-regular graphs, where we compute our upper bound on their Cheeger constants.

Original languageEnglish
Pages (from-to)507-519
Number of pages13
JournalBulletin of the Korean Mathematical Society
Volume54
Issue number2
DOIs
StatePublished - 2017

Bibliographical note

Funding Information:
The second named author is a corresponding author and supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2009-0093827) and also by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST)(2014-002731).

Publisher Copyright:
© 2017 Korean Mathematical Society.

Keywords

  • Cheeger constant
  • Cheeger inequality
  • Distance-regular graph
  • Green’s function
  • Laplacian
  • P-polynomial scheme

Fingerprint

Dive into the research topics of 'An upper bound on the Cheeger constant of a distance-regular graph'. Together they form a unique fingerprint.

Cite this