關於幾類正則圖形值譜性值之研究

Abstract

一個直徑為 d 的正則連通圖的相異特徵值個數大於或等於d +1，並且我們也知道一個直 徑為d 的距離正則圖的相異特徵值個數恰等於d +1，反之不然。作為一個極值圖形族來 看，直徑為d 且具有d +1個相異特徵值的正則連通圖值得作深入的研究。針對這項目 標，在這項為期三年的研究計畫裏，我們擬就下列三項問題作詳細的探討。 一、 對一個直徑為 d 且具有d +1個相異特徵值的正則連通圖而言，如d = 2，其必為強 正則；對於d = 3的情形，我們已知道部份的結果；探討d ≤ 5時的情形，是本計畫 的重點之一。 二、全部的距離正則圖和部份已知的路徑正則圖均屬於前述的極值圖形族，我們擬引進 部份距離正則和部份路徑正則兩概念，作為距離正則和路徑正則概念的推廣，以 期能發現更多屬於前述極值圖形族的圖。 三、若干和 Johnson 圖、Grassmann 圖共譜或共參數的正則連通圖已陸續構作出來；由 於雙線形圖和Johnson 圖、Grassmann 圖的幾何結構的關連性，我們預期雙線形圖 亦將有相近似的結果。 四、探討直徑為 d 且具有d +1個相異特徵值的正則連通圖可能的組合意義。 我們預期上述的研究結果，將會有助於我們對直徑為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. Toward this goal, the following topics will be among the focuses of this research: 1. For those regular graphs of diameter d with exactly d+1distinct eigen values, they are strongly regular whenever d = 2 , some partial conditions were known to the case d = 3; study of the cases d ≤ 5 will be included in this project; 2. 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-walk- regular, so that more graphs belong to this extremal family can be derived; 3. 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. 4. Collect examples of connected regular graphs of diameter d with d+1 distinct eigenvalues as many as possible, and study possible combinatorial interpretations of those graphs. 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 studies.