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

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

中圖分類號(hào)：G420 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1673-9795（2013）08（a）-0148-02

1 序言

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

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

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

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

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

2 主要結(jié)果

引理1：令，如果并且，

則。

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

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

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

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

引理3：如果是圖上的一個(gè)等價(jià)劃分，則的特征多項(xiàng)式整除的特征多項(xiàng)式。

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

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

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

，，

因此，。

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

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

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

證明：我們考察的情形。

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

因此，

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

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

證明：我們考察。

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

因此，

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

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

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

定理7：≤1當(dāng)且僅當(dāng)。

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

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

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

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

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

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

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

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

因此，

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

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

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

因此，

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

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

參考文獻(xiàn)

[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.