AN UPPER BOUND ON THE CHEEGER CONSTANT OF A DISTANCE-REGULAR GRAPH

作者：Kim Gil Chun^*; Lee Yoonjin

来源：Bulletin of the Korean Mathematical Society, 2017, 54(2): 507-519.

DOI：10.4134/BKMS.b160157

• Green's function
• Laplacian
• P-polynomial scheme
• distance regular graph
• Cheeger constant
• Cheeger inequality

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.

• 出版日期2017-3