An upper bound on the Cheeger constant of a distance-regular graph
Bull. Korean Math. Soc. 2017 Vol. 54, No. 2, 507-519
https://doi.org/10.4134/BKMS.b160157
Published online March 31, 2017
Gil Chun Kim and Yoonjin Lee
Dong-A University, Ewha Womans University
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 $\beta$-Laplacian for some positive real number $\beta$. We present some examples of distance-regular graphs, where we compute our upper bound on their Cheeger constants.
Keywords : Green's function, Laplacian, $P$-polynomial scheme, distance-regular graph, Cheeger constant, Cheeger inequality
MSC numbers : 05C40, 05C50
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd