TY - JOUR

T1 - A spectral excess theorem for nonregular graphs

AU - Lee, Guang Siang

AU - Weng, Chih-wen

PY - 2012/10/1

Y1 - 2012/10/1

N2 - The spectral excess theorem asserts that the average excess is, at most, the spectral excess in a regular graph, and equality holds if and only if the graph is distance-regular. An example demonstrates that this theorem cannot directly apply to nonregular graphs. This paper defines average weighted excess and generalized spectral excess as generalizations of average excess and spectral excess, respectively, in nonregular graphs, and proves that for any graph the average weighted excess is at most the generalized spectral excess. Aside from distance-regular graphs, additional graphs obtain the new equality. We show that a graph is distance-regular if and only if the new equality holds and the diameter D equals the spectral diameter d. For application, we demonstrate that a graph with odd-girth 2. d+. 1 must be distance-regular, generalizing a recent result of van Dam and Haemers.

AB - The spectral excess theorem asserts that the average excess is, at most, the spectral excess in a regular graph, and equality holds if and only if the graph is distance-regular. An example demonstrates that this theorem cannot directly apply to nonregular graphs. This paper defines average weighted excess and generalized spectral excess as generalizations of average excess and spectral excess, respectively, in nonregular graphs, and proves that for any graph the average weighted excess is at most the generalized spectral excess. Aside from distance-regular graphs, additional graphs obtain the new equality. We show that a graph is distance-regular if and only if the new equality holds and the diameter D equals the spectral diameter d. For application, we demonstrate that a graph with odd-girth 2. d+. 1 must be distance-regular, generalizing a recent result of van Dam and Haemers.

KW - Distance-regular graphs

KW - Eigenvalues

KW - Spectral excess theorem

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

U2 - 10.1016/j.jcta.2012.04.002

DO - 10.1016/j.jcta.2012.04.002

M3 - Article

AN - SCOPUS:84859718677

SN - 0097-3165

VL - 119

SP - 1427

EP - 1431

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 7

ER -