圖和線圖的鄰接譜及拉普拉斯譜的關系

摘 要：圖譜理論是圖論研究的重要領域之一，也是非常活躍的研究方向。實踐表明，對特征值的計算十分復雜，但可以研究不同定義的譜之間的關系確定特征值的上下界。通過利用對稱矩陣和半正定矩陣的一些性質，討論簡單無向圖G及其線圖Gl的鄰接譜之間的一些關系，推廣已有的結果。同時也討論圖的鄰接譜和拉普拉斯譜之間的關系。對判定某些圖的鄰接譜和拉普拉斯譜的范圍具有一定的指導作用。

關鍵詞：圖；線圖；特征值；譜；拉普拉斯譜

中圖分類號：O157.5；TP393 文獻標識碼：B 文章編號：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 預備知識

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

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

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

下面介紹2個引理。

引理1^[2]設A，B是實對稱矩陣，則對k=1，2，…，n，有：

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

引理2^[2] 設A，B是實對稱矩陣，且B是半正定矩陣，則k=1，2，…，n有：

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

2 圖和線圖的特征值之間的關系

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

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

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

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

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

定理2 設圖G的頂點度序列為Δ=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 設圖G的頂點度序列為Δ=d1≥d2≥…≥dn=δ，則有：

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

推論 2 設圖G的頂點度序列為Δ=d1≥d2≥…≥dn=δ，則有：

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

推論 3 設圖G的頂點度序列為Δ=d1≥d2≥…≥dn=δ，則有：

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

3 圖的特征值和拉普拉斯特征值之間的關系

定理3 設圖G的頂點度序列為Δ=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

由矩陣知識可知，對任意矩陣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)} 

參 考 文 獻

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

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。