圖譜剩餘定理及其應用

Abstract

圖譜剩餘定理 (Spectral excess theorem) 用於刻劃一個正則圖是否為距離正則圖。存在例子顯示出圖譜剩餘定理無法直接應用於非正則圖，為了使其可應用於非正則圖，在這篇論文中，我們給出一個加權版本的圖譜剩餘定理，並且用此加權版本來證明奇圍長定理 (Odd-girth theorem)，此結果解決了 E.R. van Dam 和 W.H. Haemers 兩位學者在一篇論文中所提出的問題。接著，我們應用圖譜剩餘定理及其證明的精神到二分圖的研究。眾所周知，一個二分距離正則圖的兩個半圖 (halved graphs) 皆為距離正則圖。首先我們提供幾個例子來說明兩個半圖皆為距離正則圖的二分圖不一定會是距離正則圖，然後證明在一些附加條件之下，此二分圖將會是距離正則圖。

The spectral excess theorem gives a quasi-spectral characterization for a regular graph to be distance-regular. An example demonstrates that this theorem cannot be directly applied to nonregular graphs. In order to make it applicable to nonregular graphs, a `weighted' version of the spectral excess theorem is given. As an application, we show that a connected graph with $d+1$ distinct eigenvalues and odd-girth $2d+1$ is distance-regular, generalizing a result of van Dam and Haemers. We then apply this line of study to the class of bipartite graphs. It is well-known that the halved graphs of a bipartite distance-regular graph are distance-regular. Examples are given to show that the converse does not hold. Thus, a natural question is to find out when the converse is true. We give a quasi-spectral characterization of a connected bipartite weighted $2$-punctually distance-regular graph whose halved graphs are distance-regular. In the case the spectral diameter is even we show that the graph characterized above is distance-regular.