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

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

關(guān)鍵詞：積圖 第二大特征值

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

1 序言

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

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

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

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

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

2 主要結(jié)果

引理1：令，如果并且，

則。

由引理1我們可以看出，若是的導(dǎo)出子圖，則。

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

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

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

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

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

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

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

，，

因此，。

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

從而，我們知道：結(jié)論成立。

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

證明：我們考察的情形。

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

因此，

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

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

證明：我們考察。

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

因此，

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

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

從而，我們知道結(jié)論成立。

定理7：≤1當且僅當。

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

。于是由引理2知道，結(jié)論成立。

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

證明：根據(jù)MATLAB，我們知道，，。由引理1知道，結(jié)論成立。

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

證明：根據(jù)MATLAB，，，。這樣根據(jù)引理1，我們知道結(jié)論成立。

定理10：設(shè)2≤≤。那么。

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

因此，

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

定理11：設(shè)2≤≤。那么。

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

因此，

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

至此，我們確定了積圖中由所構(gòu)成的所有滿足第二大特征值不超過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.