關於圖形的值譜及其距離正則性的研究

Abstract

一個直徑為d 的正則連通圖的相異特徵值個數大於或等於d +1，並且一 個直徑為d 的距離正則圖的相異特徵值個數恰等於d +1，反之不然。作為一 個極值族來看，直徑為d 且具有d +1個相異特徵值的正則連通圖值得作深入 的研究。 全部的距離正則圖和部份已知的路徑正則圖均屬於前述的極值族，我 們擬引用“局部距離正則＂和“局部路徑正則＂的概念，作為距離正則和 路徑正則概念的推廣，以期能發現更多屬於前述極值族的圖形。同時，若 干和Johnson 圖、Grassmann 圖共譜或共參數的正則連通圖已陸續構作出 來；由於雙線形圖和Johnson 圖、Grassmann 圖的幾何結構的關連性，我們 預期雙線形圖亦將有相近似的結果。 我們預期上述的研究，將會有助於我們對直徑為d 且具有d +1個相異特 徵值的極值圖形族的瞭解。

Each connected regular graph of diameter d has at least d+1 distinct eigenvalues, and it is also known that each distance-regular graph of diameter d has exactly d+1 distinct eigenvalues, though the converse is not true. As an extremal family, those connected regular graphs of diameter d with exactly d+1 distinct eigenvalues deserve further study. Since all distance-regular graphs and some known walk-regular graphs are among this extremal family, the conditions of distance regular and walk regular will be relaxed by introducing the notions of t-distance regular and t-walkregular, so that more graphs belong to this extremal family can be derived. Moreover, some cospectral mates and distance-regular mates of some Johnson graphs and Grassmann graphs have been found, similar situations may occur to the bilinear forms graphs due to their close relationships. We expect that our understanding of those regular graphs of diameter d with exactly d+1 eigen values will be benefited from the above mentioned study.