An upper bound on the Cheeger constant of a distance-regular graph
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (16)
- E. Bannai, "Algebraic Combinatorics I: Association Schemes", pp.1984, Benjamin
- N. Biggs, "Algebraic Graph Theory" (1974), Cam-bridge University Press
- A. Brouwer, "Eigenvalues and perfect matchings", Linear Algebra Appl, 395, pp.155~162 (2005)
- A. Brouwer, "The vertex-connectivity of a distance regular-graph", Eu-ropean J. Combin, 30(3), pp.668~673 (2009)
- F. Chung, "Fete of Combinatorics and Computer Science", pp.43~62 (2010), Springer
- F. Chung, "PageRank as a discrete Green’s function, Geometry and Analysis. No. 1", Adv. Lect. Math. (ALM), 17, pp.285~302 (2011), Int. Press
- F. Chung, "Covering, heat kernels and spanning tree", Electron. J. Combin, 6, pp.21~ (1999)
- P. Delsarte, "An algebraic approach to the association schemes of coding theory", Philips Res. Rep. Suppl, 10, pp.97~ (1973)
- 85), "From local times to global geometry, control and physics (Coventry, 1984", pp.1986, J. Dodziuk
- 김길천, "Explicit expression of the Krawtchouk polynomial via a discrete Green's function", 대한수학회지, 50(3), pp.509~527 (2013), 대한수학회
- G. C. Kim, "A Cheeger inequality of a distance regular graph using Green’s function", Dis-crete Math, 313(20), pp.2337~2347 (2013)
- G. C. Kim, "A Cheeger inequality of a distance-regular graph using Green’s function", Discrete Math, 338(9), pp.1621~1623 (2015)
- J. H. Koolen, "An inequality involving the second largest and smallest eigenvalue of a distance regular graph", Linear Algebra Appl, 434(12), pp.2404~2412 (2011)
- G. Oshikiri, "Cheeger constant and connectivity of graphs", Interdiscip. Inform. Sci, 8(2), pp.147~150 (2002)
- J. Tan, "On cheeger inequalities of a graph", Discrete Math, 269(1-3), pp.315~323 (2003)
- P. Terwilliger, "An inequality involving the local eigenvalues of a distance-regular graph", J. Algebraic Combin, 19(2), pp.143~172 (2004)