標題: A spectral excess theorem for nonregular graphs
作者: Lee, Guang-Siang
Weng, Chih-wen
應用數學系
Department of Applied Mathematics
關鍵字: Distance-regular graphs;Eigenvalues;Spectral excess theorem
公開日期: 1-十月-2012
摘要: 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 2d + 1 must be distance-regular, generalizing a recent result of van Dam and Haemers. (C) 2012 Elsevier Inc. All rights reserved.
URI: http://hdl.handle.net/11536/16403
ISSN: 0097-3165
期刊: JOURNAL OF COMBINATORIAL THEORY SERIES A
Volume: 119
Issue: 7
結束頁: 1427
顯示於類別:期刊論文


文件中的檔案:

  1. 000305820200004.pdf