第二大特征值不超過1的一些積圖

摘 要：在這篇文章里，我們討論了一些第二大特征值不超過1的一些特殊積圖類型。涉及到的相關概念：特征值、積圖、幾種特殊類型的圖，會在序言中詳細給出。

關鍵詞：積圖 第二大特征值

中圖分類號：G420 文獻標識碼：A 文章編號：1673-9795（2013）08（a）-0148-02

1 序言

為了方便下述工作的進行，先介紹一些基本概念。我們將圖G通常寫成的形式，這里，分別表示圖G的點集和邊集。如果在點和之間有一條屬于的邊連接，則稱點和點是相鄰的，或稱點是點的一個鄰點，也稱邊與點和點是關聯的。和點關聯的邊的數目稱為點的度。設是的一個任意的頂點集，即，那么由導出的G的子圖指的是以為頂點集，在中任意兩點的鄰接關系與這兩個點在作為中點時的鄰接關系保持一致的圖。令是一個頂點集為的圖，它的鄰接矩陣記為，定義如下：如果與相鄰，那么；否則。圖的特征多項式是，記作。矩陣是實對稱矩陣，我們假設≥≥…≥是的全部特征值，并且這些特征值與圖的頂點的排列順序無關，即它們不依賴于的頂點順序。我們也記（），則稱為圖的譜。其中稱為圖的鄰接矩陣的第大特征值，顯然，是圖的鄰接矩陣的最大特征值，（有時也被稱為指數），并且我們將它稱為圖的譜半徑，是第二大特征值。

設X和Y是兩個簡單圖，它們的積圖具有頂點集，且積圖中的點與相鄰當且僅當或者或者，這里。

下面介紹幾種特殊類型的圖：若中每個頂點的度均為2，則稱為圈。長為的路表示一個起于終于的個相異點的序列，并且連續的點之間是相鄰的。一個圖中每一對不同的頂點都有一條邊相連，稱為完全圖。二部圖是指一個圖，它的頂點集可以分解成兩個子集X和Y，使得任何一條邊都有一個端點在X 中，而另一個端點在Y中。（我們把這樣一種分類稱為圖的一個二分類）。完全二部圖是指具有二分類的簡單二部圖，其中X 的每個頂點都與Y的每個頂點相連，若，，我們將這樣的完全二部圖記為。接下來，我們將用和分別表示有個點的圈，路，完全圖，用表示兩部分分別為的完全二部圖。

Cvetkovic在1981年提出了這樣一個問題：是否有可能確定所有第二大特征值不超過1的圖類？在隨后的一些年里，人們已經得到了關于這個問題的一些結果。其中，Y.Hong在文獻[4]中確定了所有的樹；J.L.Shu在文獻[5]中確定了所有≤1的樹，G.H.Xu在文獻[6]中確定了所有≤1的單圈圖；S.G.Guo在文獻[3]中確定了所有≤1的雙圈圖。

在這篇文章里，我們分別取X和Y為，，進而確定了一些第二大特征值不超過1的一些特殊的積圖類型。

2 主要結果

引理1：令，如果并且，

則。

由引理1我們可以看出，若是的導出子圖，則。

引理2：圈的譜是，路的譜是。

根據引理1和2，我們有以下結論：對于≤1的簡單圖，它既不包含長大于6的導出圈，也不包含長大于4的導出路。

設是的一個劃分，，如果中的任意一點在中的鄰點的個數都是恒定的，則稱是的一個等價劃分。用的這個元素作為個點，用表示中連接第個元素到第個元素的邊的條數，我們按這種方法做出的圖叫做在上的商集，且該商集的鄰接矩陣為。

引理3：如果是圖上的一個等價劃分，則的特征多項式整除的特征多項式。

根據上述定義和引理，我們將逐步得出下面的主要結果。

定理4：設和是兩個完全圖，其≥≥中。那么≤1當且僅當。

證明：令，。為了記法簡單，我們將積圖中的點記為，其中1≤i≤3，1≤j≤m。容易看出，有一個由以下3個部分構成的等價劃分。

，，

因此，。

容易看出（二重根）是的三個特征值，根據引理3我們知道，也是的特征值，并且≥。這樣，只有=3時，才有可能不大于1。又由MATLAB知道，。

從而，我們知道：結論成立。

定理5：設是一個≥3階的完全圖，是一個≥4長的圈。那么。

證明：我們考察的情形。

令，。為了記法簡單，我們將積圖中的點記為，其中1≤i≤4，1≤j≤n。容易看出，有一個由以下4個部分構成的等價劃分。

因此，

容易得出，，（二重根），是的四個特征值，根據引理3我們知道，，，也是的特征值，并且≥。容易看出，當n≥3時，≥2。由MATLAB知道，。這樣根據引理3，我們有。類似地可以證明，。于是根據引理2，我們知道結論成立。

定理6：設是一個完全圖，是一條路，其中n≥3，m≥3。那么≤1當且僅當。

證明：我們考察。

令，，為了記法簡單，我們將積圖中的點記為，其中1≤i≤3，1≤j≤n。容易看出，有一個由以下3個部分構成的等價劃分。

因此，

容易得出，，，是的三個特征值，根據引理3，我們知道，，，也是的特征值，并且≥。容易看出，n≥3時，≥2。

這樣根據，引理3，我們有。又由MATLAB，知道。

從而，我們知道結論成立。

定理7：≤1當且僅當。

證明：由MATLAB可知，，，，，

。于是由引理2知道，結論成立。

定理8：設n≥2，m≥2。那么≤1當且僅當或3。

證明：根據MATLAB，我們知道，，。由引理1知道，結論成立。

定理9：設n≥2，2≤≤。那么≤1當且僅當。

證明：根據MATLAB，，，。這樣根據引理1，我們知道結論成立。

定理10：設2≤≤。那么。

證明：我們考察。令 ，。我們將積圖中的點（x，y）記為的形式。容易看出，有一個由以下6個部分構成的等價劃分。

因此，

通過計算，我們得出（其中，均為二重根），0是的特征值，根據引理3我們知道，這些根也是的特征值，并且≥。當時，，這樣根據引理3我們有。同樣地可以證明，，。于是由引理2，結論成立。

定理11：設2≤≤。那么。

證明：我們考察。令， ，將積圖中的點（x，y）記為的形式。容易看出，有一個由以下8個部分構成的等價劃分。

因此，

通過計算，我們可以得出，0，1，-1為的5個特征值。由此我們斷定。根據引理3，。于是由引理1，我們知道，結論成立。

至此，我們確定了積圖中由所構成的所有滿足第二大特征值不超過1的圖類。

參考文獻

[1]D.Cvetkovic.On graphs whose second largest eigenvalue does not exceed 1[J].Pub1.Inst.Math（Beograd），1982，31（45）：15-20.

[2]C.Godsil， Gordon Royle.Algebraic Graph Theory[M].New York：Springer Verlag，2001.

[3]Shu-Guang Guo.On bicyclic graphs whose second largest eigenvalue does not exceed 1[J].Linear Algebra and its Applications，2005（407）：201-210.

[4]Y.Hong.Sharp low bounds on the eigenvalues of tree[J]. Linear Algebra And Its Apllication，1980（113）：101-105.

[5]J.LShu.On trees whose second largest eigenvalues does not exceed 1[J].OR Trans，1998，2（13）：6-9.

[6]G.H.Xu.On uncyclic graph whose second largest eigenvalue does not exceed 1[J].Discrete Application Mathematics，2004（136）：117-124.