TY - JOUR

T1 - Some Results on the Eigenvalues of Distance-Regular Graphs

AU - Bang, Sejeong

AU - Koolen, Jack H.

AU - Park, Jongyook

N1 - Publisher Copyright:
© 2015, Springer Japan.

PY - 2015/9/2

Y1 - 2015/9/2

N2 - In 1986, Terwilliger showed that there is a strong relation between the eigenvalues of a distance-regular graph and the eigenvalues of a local graph. In particular, he showed that the eigenvalues of a local graph are bounded in terms of the eigenvalues of a distance-regular graph, and he also showed that if an eigenvalue θ of the distance-regular graph has multiplicity m less than its valency k, then -1-b1θ+1 is an eigenvalue for any local graph with multiplicity at least k-m. In this paper, we are going to generalize the results of Terwilliger to a broader class of subgraphs. Instead of local graphs, we consider induced subgraphs of distance-regular graphs (and more generally t-walk-regular graphs with t a positive integer) which satisfies certain regularity conditions. Then we apply the results to obtain bounds on eigenvalues of t-walk-regular graphs if the girth equals 3, 4, 5, 6 or 8. In particular, we will show that the second largest eigenvalue of a distance-regular graph with girth 6 and valency k is at most k-1, and we will show that the only such graphs having k-1 as its second largest eigenvalue are the doubled Odd graphs.

AB - In 1986, Terwilliger showed that there is a strong relation between the eigenvalues of a distance-regular graph and the eigenvalues of a local graph. In particular, he showed that the eigenvalues of a local graph are bounded in terms of the eigenvalues of a distance-regular graph, and he also showed that if an eigenvalue θ of the distance-regular graph has multiplicity m less than its valency k, then -1-b1θ+1 is an eigenvalue for any local graph with multiplicity at least k-m. In this paper, we are going to generalize the results of Terwilliger to a broader class of subgraphs. Instead of local graphs, we consider induced subgraphs of distance-regular graphs (and more generally t-walk-regular graphs with t a positive integer) which satisfies certain regularity conditions. Then we apply the results to obtain bounds on eigenvalues of t-walk-regular graphs if the girth equals 3, 4, 5, 6 or 8. In particular, we will show that the second largest eigenvalue of a distance-regular graph with girth 6 and valency k is at most k-1, and we will show that the only such graphs having k-1 as its second largest eigenvalue are the doubled Odd graphs.

KW - Distance-regular graph

KW - Doubled Odd graph

KW - Odd graph

KW - Spectral gap

KW - t-walk-regular graph

UR - http://www.scopus.com/inward/record.url?scp=84946472907&partnerID=8YFLogxK

U2 - 10.1007/s00373-015-1622-6

DO - 10.1007/s00373-015-1622-6

M3 - Article

AN - SCOPUS:84946472907

SN - 0911-0119

VL - 31

SP - 1841

EP - 1853

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -