AN UPPER BOUND ON THE CHEEGER CONSTANT OF A DISTANCE-REGULAR GRAPH
- 주제(키워드) Green's function , Laplacian , P-polynomial scheme , distance regular graph , Cheeger constant , Cheeger inequality
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS, KCI등재
- 발행기관 KOREAN MATHEMATICAL SOC
- 발행년도 2017
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000144752
- 본문언어 영어
- Published As http://dx.doi.org/10.4134/BKMS.b160157
초록/요약
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.
more