摘 要：圖譜理論是圖論研究的重要領(lǐng)域之一，也是非?；钴S的研究方向。實(shí)踐表明，對(duì)特征值的計(jì)算十分復(fù)雜，但可以研究不同定義的譜之間的關(guān)系確定特征值的上下界。通過(guò)利用對(duì)稱(chēng)矩陣和半正定矩陣的一些性質(zhì)，討論簡(jiǎn)單無(wú)向圖G及其線圖Gl的鄰接譜之間的一些關(guān)系，推廣已有的結(jié)果。同時(shí)也討論圖的鄰接譜和拉普拉斯譜之間的關(guān)系。對(duì)判定某些圖的鄰接譜和拉普拉斯譜的范圍具有一定的指導(dǎo)作用。

關(guān)鍵詞：圖；線圖；特征值；譜；拉普拉斯譜

中圖分類(lèi)號(hào)：O157.5；TP393 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004-373X(2008)10-123-02

Relation between the Eigenvalues of a Graph andIts Line Graph or Laplacian Eigenvalues

ZHAO Xiaoying，ZHANG Xiandi

(School of Applied Mathematics，University of Electlonic Science Technology of China，Chengdu，610054，China)

Abstract：Graph spectral theory is not only an important field in graph theory，but also special active direction.It has been proved that computing eigenvalues are quite complicated，but can study between the relationships about the spectral of the different definitions to determine the bounds of the eigenvalues.By using some characters of the real symmetrical matrix and semi-positive definite matrix，some relations on the adjacent spectrum of the simple undirected graph G and its line graph Gl are studied in this paper，the past results are generalized.At the same time，two relations between the adjacent spectrum of a graph and its Laplacian spectrum are also obtained in the paper.This is valuable to guiding the bounds of the eigenvalues estimation.

Keywords：graph;line graph;eigenvalue;spectrum;Laplacian spectrum

1 預(yù)備知識(shí)

設(shè)G=(V，E)是簡(jiǎn)單無(wú)向圖。圖G的拉普拉斯矩陣記為L(zhǎng)(G)，且L(G)=D(G)－A(G)，其中A(G)是圖G的鄰接矩陣，D(G)=diag(d(v1)，d(v2)，…，d(vn))是G的度對(duì)角矩陣。顯然L(G)是一個(gè)是實(shí)對(duì)稱(chēng)矩陣。由蓋爾圓盤(pán)定理知，他的特征值為非負(fù)實(shí)數(shù)。記n×n矩陣M的特征值為λ1(M)，λ2(M)，…，λn(M)。圖G的拉普拉斯譜是指他的拉普拉斯矩陣的所有特征值，用λi(G)(i=1，2，…，n)來(lái)標(biāo)記，且設(shè)λ1(G)≥λ2(G)≥…≥λn－1(G)≥λn(G)，眾所周知，λn(G)=0，而且0作為L(zhǎng)(G)的特征值的代數(shù)重復(fù)度等于圖G的連通分支的數(shù)量^[1]。圖的鄰接譜是指他的鄰接矩陣A(G)的所有特征值，用ρi(G)(i=1，2，…，n)標(biāo)記。圖G的擬拉普拉斯矩陣記為Q(G)，且Q(G)=D(G)+A(G)。

給定簡(jiǎn)單無(wú)向圖G=(V，E)，G的線圖記為Gl=(Vl，El)，其中Vl=E，若邊e，f∈E，且e與f在G中鄰接，則ef∈El；否則efEl。

設(shè)M是圖G的關(guān)聯(lián)矩陣，且知MMT=Q(G)=D(G)+A(G)，MTM=A(Gl)+2I，因此有λi(MMT)=λi(MTM)=ρi(Gl)+2。

下面介紹2個(gè)引理。

引理1^[2]設(shè)A，B是實(shí)對(duì)稱(chēng)矩陣，則對(duì)k=1，2，…，n，有：

λk(A)+λn(B)≤λk(A+B)≤λk(A)+λ1(B)

引理2^[2] 設(shè)A，B是實(shí)對(duì)稱(chēng)矩陣，且B是半正定矩陣，則k=1，2，…，n有：

λk(A)≤λk(A+B)

2 圖和線圖的特征值之間的關(guān)系

設(shè)G是簡(jiǎn)單無(wú)向圖，文獻(xiàn)［3］給出G與其線圖Gl的最大特征值ρ1(G)和ρ1(Gl)之間的2個(gè)關(guān)系式（見(jiàn)定理1），這里將推廣第一個(gè)關(guān)系式，給出G的任意特征值ρi(G)和ρi(Gl)之間的關(guān)系式。

定理1^[3] 設(shè)圖G的最大度數(shù)和最小度數(shù)分別為Δ和δ，則有：

2ρ1(G)－2≤ρ1(Gl)≤Δ+ρ1(G)－2

如果G是連通圖，那么任一邊等式成立的充要條件是G是正則圖。此外如果G是直徑為d的n階不規(guī)則圖，則：

ρ1(Gl)>2ρ1(G)－2+(Δ+δ－2Δδ)(dΔn)

定理2 設(shè)圖G的頂點(diǎn)度序列為Δ=d1≥d2≥…≥dn=δ，則有：

max{ρi(G)－2，2ρi(G)－2}≤ρi(Gl)≤min{Δ+ρi(G)－2，di+ρ1(G)－2}

證明 已知 λi(MMT)=λi(MTM)=ρi(Gl)+2且λi(MMT)=λi(D(G)+A(G))，因此有λi(D(G)+A(G))=ρi(Gl)+2。

由引理1及λ1(D(G))=Δ有：

λi(D(G)+A(G))[WB]=ρi(Gl)+2≤λ1(D(G))+ρi(G)

[DW]=Δ+ρi(G)

由此得：

ρi(Gl)≤Δ+ρi(G)－2（1）

再由引理1及λi(D(G))=di有：

λi(D(G)+A(G))[WB]=ρi(Gl)+2≤λi(D(G))+ρ1(G)

[DW]=di+ρ1(G)

由此得：

ρi(Gl)≤di+ρ1(G)－2（2）

因此由式（1），（2）可得：

ρi(Gl)≤min{Δ+ρi(G)－2，di+ρ1(G)－2}（3）

又知：Q(G)=MMT=D(G)+A(G)且

L(G)=D(G)－A(G)

故有：MMT=L(G)+2A(G)

再次使用引理1及λn(G)=0有：

ρi(Gl)+2[WB]=λi(L(G)+2A(G))≥2ρi(G)+λn(G)

[DW]=2ρi(G)

所以：

ρi(Gl)≥2ρi(G)－2（4）

眾所周知，D(G)是半正定矩陣，則由引理2有：

ρi(G)≤λi(A(G)+D(G))=ρi(Gl)+2

因此：

ρi(Gl)≥ρi(G)－2（5）

由式（4），（5）得：

ρi(Gl)≥max{ρi(G)－2，2ρi(G)－2}（6）

最后由式（3）和式（6）得：

max{ρi(G)－2，2ρi(G)－2}≤ρi(Gl)≤

min{Δ+ρi(G)－2，di+ρ1(G)－2}

因已知 ∑ni=1ρi(G)=0，從而有ρ1(G)≥0和ρn(G)≤0，因此定理中ρi(G)－2和2ρi(G)－2不可以比較大小，但可知δ+ρi(G)－2≥ρi(G)－2。

推論 1 設(shè)圖G的頂點(diǎn)度序列為Δ=d1≥d2≥…≥dn=δ，則有：

2ρ1(G)－2≤ρ1(Gl)≤Δ+ρ1(G)－2

推論 2 設(shè)圖G的頂點(diǎn)度序列為Δ=d1≥d2≥…≥dn=δ，則有：

ρn(G)－2≤ρn(Gl)≤min{Δ+ρn(G)－2，δ+ρ1(G)－2}

推論 3 設(shè)圖G的頂點(diǎn)度序列為Δ=d1≥d2≥…≥dn=δ，則有：

max{ρi(G)，2ρi(G)}≤μi(G)≤min{Δ+ρi(G)，di+ρ1(G)}

3 圖的特征值和拉普拉斯特征值之間的關(guān)系

定理3 設(shè)圖G的頂點(diǎn)度序列為Δ=d1≥d2≥…≥dn=δ，則有：

(1) di -ρ1 (G)≤λi (G)≤ min{2d2i+ 2ρ21 (G)， 

2Δ 2 + 2ρ2i (G)，di -ρn (G)}。

(2) λ1(G)≥maxni=1{di－ρi(G)}

證明 已知L(G)=D(G)－A(G)且Q(G)=

MMT=D(G)+A(G)

所以有：

(L(G))2=(D(G))2－2D(G)A(G)+(A(G))2（7）

和：

(Q(G))2=(D(G))2+2D(G)A(G)+(A(G))2（8）

由式（7），式（8）可得：

(L(G))2+(Q(G))2=2(D(G))2+2(A(G))2

由矩陣知識(shí)可知，對(duì)任意矩陣A有λ(A2)=λ2(A)和λ(nA)=nλ(A)成立，又顯然(Q(G))2是半正定矩陣，所以由引理1和2有：

λ2i (G)≤λi ((L(G))2 + (Q(G))2) = λi (2(D(G))2 +

2(A(G))2)≤min{λi(2(D(G))2)+λ1(2(A(G))2)，

λi(2(A(G))2)+λ1(2(D(G))2)}≤min{2λ2i (D(G)) +

2ρ21 (G)，2λ21 (D(G)) + 2ρ2i (G)}≤min{2d2i+ 2ρ21 (G)，

2Δ 2 + 2ρ2i (G)}

因此：

λi (G)≤min{2d2i+ 2ρ21 (G)， 2Δ 2 + 2ρ2i (G)} （9）

又有：

λi(G)+ρn(G)≤λi(L(G)+A(G))=λi(D(G))

≤λi(G)+ρ1(G)（10）

和：

λn(G)+ρn(G)≤λi(L(G)+A(G))=λi(D(G))

≤λ1(G)+ρi(G)（11）

故由式（10），（11）有：

di－ρ1(G)≤λi(G)≤di－ρn(G)（12）

和：

λ1(G)≥maxni=1{di－ρi(G)}（13）

又知2d2i + 2ρ21 (G)， 2Δ 2 + 2ρ2i (G)，di -ρn (G)是不可比較大小的。

那么由式（9），（12）有：

di -ρ1 (G)≤λi (G)≤ min{2d2i + 2ρ21 (G)，

2Δ 2 + 2ρ2i (G)，di -ρn (G)} 

參 考 文 獻(xiàn)

［1］Merris R.Laplacian Matrices of Graphs:A Survey［J］.Linear Algebra Appl.，1998:143-176.

［2］Cvetkovic D，Doob M，Sachs H.Spectra of Graphs［M］.Theory and Appl.，Academic Press，New York，1980.

［3］Shi Lingsheng.The Spectral Radii of a Graph and Its Line Graph［J］.Linear Algebra Appl.，2006:58-66.

［4］Nordhaus E A，Gaddum J M.On Complementary Graphs［J］.Amer.Math.Monthly，1956，63:175-177.

［5］Shi Lingsheng.Bounds on the (Laplacian) Spectral Radius of Graphs［J］.Linear Algebra Appl.，2007:755-770.

［6］Li Jongsheng，Pan Yongliang.de Cane`s.Inequality and Bounds on the Largest Laplacian Eigenvalue of a Graph［J］.Linear Algebra Appl.2001:153-160.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。