A spectral excess theorem for nonregular graphs

檔案

日期

2012-10-01

類型

期刊名稱

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷期與頁次

第 119 卷第 7 期

ISSN

0097-3165

語言

英文

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Lee, G.-S., & Weng, C.-W. (2012). A spectral excess theorem for nonregular graphs. JOURNAL OF COMBINATORIAL THEORY SERIES A, 119(7). https://ir.lib.nycu.edu.tw/handle/11536/16403

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/16403