圖的譜半徑與擬懸掛點數

劉存磊, 汪 毅, 范益政

(安徽大學數學科學學院,安徽合肥 230039)

圖的譜半徑與擬懸掛點數

劉存磊, 汪 毅, 范益政

(安徽大學數學科學學院,安徽合肥 230039)

設G(n,k)為含有k個擬懸掛點的n階圖所構成的集合.本文刻畫了在G(n,k)中無符號Laplace譜半徑達到最大的圖,同時給出了當k=0,1,2,3時,在G(n,k)中無符號Laplace譜半徑達到最小的圖.

圖;無符號Laplace矩陣;譜半徑;擬懸掛點

1 引 言

設G=(V,E)是一個n階簡單圖,其中V={v1,v2,…,vn}為G的頂點集,E={e1,e2,…,em}為G的邊集.圖G的鄰接矩陣定義為A(G)=(aij)n×n,其中,當vi,vj鄰接時aij=1,否則aij=0.圖G的不定向關聯矩陣定義為M(G)=(mij)n×m,其中當vi與ej關聯時,mij=1;否則,mij=0.若給G的每條邊指定一個方向,定義Q(G)=(qij)n×m為G的定向關聯矩陣,其中當vi是ej的起點時,qij=1;當vi是ej的終點時,qij=-1;當vi與ej不關聯時,qij=0.記D(G)=diag{d1,d2,…,dn}為G的度對角矩陣,其中di為vi的度.通常意義下圖G的Laplace矩陣定義為L(G)=D(G)-A(G)(參見[1,2]).等價地,L(G)可寫成Q(G)Q(G)T,其中Q(G)為G的定向關聯矩陣.類似地,定義K(G)=M(G)M(G)T為圖G的無符號(不定向,擬)Laplace矩陣(參見[3,4]).不難發現,K(G)=D(G)+A(G).本文僅討論圖的無符號Laplace矩陣.

對于連通圖G,K(G)是一個對稱的,半正定的非負不可約矩陣.因此,K(G)的特征值均為非負實數,可將其排列為λ1≥λ2≥……≥λn≥0.集合S(G)={λ1,λ2,……λn}稱為K(G)的譜(或G的無符號Laplace譜),最大特征值λ1即為K(G)的譜半徑,記為μ(G).類似地,A(G)的最大特征值即為A(G)的譜半徑,記為ρ(G).由于K(G)(或A(G))是非負不可約矩陣,由Perron-Frobenius定理,μ(G)(或ρ(G))是單重的,且對應著唯一的(在相差一個常數的意義下)分量全正的特征向量.習慣上,分別稱ρ(G)和μ(G)為圖G的鄰接譜半徑和無符號Laplace譜半徑,稱ρ(G)和μ(G)所對應的正特征向量為A(G)和K(G)的Perron向量.

另外,M(G)TM(G)=2Im+A(GL),其中GL為G的線圖(即以G的邊為GL的頂點,GL中兩個頂點鄰接當且僅當這兩條邊在G中是鄰接的).由于M(G)TM(G)和M(G)M(G)T具有相同的非零特征值,則

上述關系建立了圖的鄰接譜半徑和無符號Laplace譜半徑之間的關系.我們常利用圖的鄰接譜半徑的一些結果來討論圖的無符號Laplace譜半徑.

近半個世紀以來,圖的鄰接譜一直是譜圖理論的熱點研究課題,國內外眾多知名學者在該領域做了大量有意義的工作.近年來,圖的無符號Laplace譜引起了人們越來越多的關注.范益政和Tam[5]等人討論了固定階數的雙圈圖譜半徑問題.Desai和Rao[6]討論了K(G)的最小特征值與圖G二部性之間的關系.其它一些關于無符號Laplace譜的結果,參見[3,7].

研究圖的各種矩陣表示的譜是為了通過譜來刻畫圖的拓撲結構性質.Dam和Haemers[8]比較了階數不超過11個的所有圖中具有相同鄰接譜和相同無符號Laplace譜的圖各自所占的比例.由比較結果發現,相對于圖的鄰接譜,無符號Laplace譜能更好地反應圖的結構性質.這也許就是近年來圖的無符號Laplace譜理論研究非常活躍的原因所在.

2 預備知識

設G=(V,E)為一個n(n≥3)階連通圖,u為G中一個頂點.與u鄰接的頂點稱為u的鄰點,u所有鄰點的集合稱為u的鄰域,記為NG(u)或N(u).u在G的度記為dG(u)或du.若dG(u)=1,則稱u為G的一個懸掛點,并稱u的鄰點為擬懸掛點.顯然,圖G擬懸掛點的個數不超過n/(n,k)為含有k個擬懸掛點的n階圖構成的集合.記G[U]為G中由頂點集U誘導的子圖.若u,v為G中不鄰接的兩個頂點,記G+uv為G添加邊uv所構成的圖.分別記Pn,Cn,Kn為n階的路、圈和完全圖.

設uv是G的一條邊,在G上刪去邊uv,添加一個新的頂點w和邊uw,vw(即將邊uv替換成一條長度為2的路uwv)所得的圖記為Guv,稱Guv是G關于邊uv的細分圖.稱下面兩種類型的路為內路:

(i)由互不相同頂點序列v0,v1,…,vk+1(k≥0)構成,其中dv0≥3,dvk+1≥3,di=2(i=1,2,…,k).

(ii)由點列v0,v1,…,vk+1(k≥2)構成,其中v1,v2,…,vk互不相同,v0=vk+1,dv0=dvk+1≥3, di=2(i=1,2,…,k).

未介紹詳盡的術語和符號可參見[9].

設G的頂點集V(G)={v1,v2,…,vn},x=(x1,x2,…xn)T∈Rn為n維列向量.可以認為x為定義在V(G)上的一個映射,即x(vi)=xi(i=1,2,…n).此時,稱xi為vi的賦值,記為xvi.由于K(G)=M(G)M(G)T,則

由Courant-Fisher定理,

其中當且僅當x(或-x)為K(G)的Perron向量時上式取到最大.若x=(x1,x2,…xn)T∈Rn是K(G)關于特征值λ的特征向量,則由K(G)x=λx可得

該方程稱為K(G)關于特征值λ的特征向量方程.

本文主要討論了固定擬懸掛點數的圖的無符號Lapalce譜半徑問題,刻畫了在圖類G(n,k)中無符號Lapalce譜半徑達到最大的唯一圖,并給出了當k=0,1,2,3時,G(n,k)中無符號Lapalce譜半徑達到最小的圖.

3 主要結果

引理3.1 設u,v為圖G中不鄰接的兩個頂點,則μ(G)＜μ(G+uv).

證設x為K(G)的單位Perron向量,由式(2.2)

定理3.2 在G(n,k)中的所有圖中,G＊是唯一的具有最大的無符號Laplace譜半徑,其中G＊是在Kn-k的k頂點上分別粘合一條懸掛邊所構成的圖.

證若k=0,結論顯然成立.設.對于G(n,k)中任意一個圖G(G≠G＊),下證μ(G)＜μ(G＊).不妨假設G的擬懸掛點為v1,v2,…,vk.對每個vi(i=1,2,…,k),取其鄰接的一個懸掛點,設為ui.記U={u1,u2,…,uk},G′=G[V(G)U].顯然G′≠Kn-k,否則G=G＊.因此可在G′內添加所有可能的邊,從而把圖G變換為圖G＊.由引理3.1,μ(G)＜μ(G＊).故結論成立.

下面討論,G(n,k)(k=0,1,2,3)中無符號Lapalce譜半徑達到最小的圖.

引理3.3[10]設G為簡單連通圖,uv為G內路上的一條邊,Guv是G關于邊uv的細分圖,則μ(Guv)＜μ(G).

定理3.4 在G(n,0)(n≥3)中的所有圖(即不含擬懸掛點的圖)中,圈Cn是唯一具有最小的無符號Laplace譜半徑的圖.

證設G為G(n,0)中具有最小無符號Laplace譜半徑的一個圖.由于G不含擬懸掛點,則G不含懸掛點,故G不是樹,從而含圈.設G中的最小長度的圈為Cm.若m＜n,則利用引理3.1,可得μ(G)＞μ(Cm)=μ(Cn).然而Cn∈G(n,0),矛盾!因此,m=n,即G=Cn.

定理3.5 在G(n,1)(n≥5)中的所有圖(即恰含1個擬懸掛點的圖)中,C是唯一具有最小的無符號Laplace譜半徑的圖,其中C是由Cn-1的某個頂點上粘合一條懸掛邊所得.

證設G為在G(n,1)中具有最小的無符號Laplace譜半徑的一個圖.若G是一個樹,則G必然是一個星圖,此時μ(G)=n≥5.否則G至少包含一個圈.若G含圈,設G中的最小長度的圈為Cm.顯然m＜n,否則G無懸掛點,從而也沒有擬懸掛點.若m＜n-1,則G必包含子圖.由引理3.1, μ(G)＞μ().由于C可認為是由C的邊不斷細分所得到的圖,由引理3.3,μ()＞μ(C),矛盾.因此,m=n-1,即G=C.根據[3,13]中結論,μ(C)＜max{du+dv∶uv∈E(C)}=5.故結論成立.

定理3.6 對于G(n,2)(n≥4)中的所有圖(即恰含2個擬懸掛點的圖),路Pn是唯一具有最小的無符號Laplace譜半徑的圖.

證設G為G(n,2)中具有最小的無符號Laplace譜半徑的一個圖,則G或是樹,或含有圈.若G是樹,則由[14]中的結論,G顯然是路Pn.若G含有圈C且G≠C,則由引理3.1,μ(G)＞μ(C)=4＞2+2cos(π/n)=μ(Pn).故結論成立.

設k,l為非負整數.設G為連通圖且含邊uv,du＞1,dv＞1.記Gk,l(u,v)是由G在其u,v兩點上分別粘合上路Pk+1和Pl+1所得到的圖.類似地,設G為連通圖且含非孤立點u,記Gk,l(u)是由G在u點上分別粘合上路Pk+1和Pl+1所得到的圖.

引理3.7[11]若k≥l≥1,則ρ(Gk,l(u,v))＞ρ(Gk+1,l-1(u,v)).

引理3.8 若k≥l≥2,則μ(Gk,l(u))＞μ(Gk+1,l-1(u)).

證在圖Gk,l(u)中,記uu′為路Pk+1上的邊,uv′為路Pl+1上的邊.則Gk,l(u)的線圖Gk,l(u)L即是Hk-1,l-1(uu′,uv′),其中H是圖G添加懸掛邊uu′和uv′后的線圖.根據引理3.7,

因而,根據公式(1.1),可知結論成立.

定理3.9 對于G(n,3)(n≥6)中的所有圖(即恰含3個擬懸掛點的圖),圖P是唯一具有最小的無符號Laplace譜半徑的圖,其中P是由路Pn在其與某個端點距離為2的點處添加一條懸掛邊而得.

證設G為G(n,3)中具有最小的無符號Laplace譜半徑的一個圖,則G或是樹,或含有圈.若G是樹,則G有圖3.1(1)結構.設G′是把G中的與v,p,w鄰接的懸掛邊分別換成等邊數的路所得到的圖,見圖3.1(2).若v,p,w中有一個點鄰接的懸掛邊大于1,則A(GL)≥(≠)A(G′L),從而ρ(GL)＞ρ(G′L).根據(1.1),μ(G)＞μ(G′),矛盾.因此,G有圖3.1(2)的結構.根據引理3.8可知G即為圖.

圖3.1 擬懸掛點數為3的兩個樹

[1] Anderson W N and Morely T D.Eigenvalues of the Laplacian of a graph[J].Linear Multilinear Algebra,1985(18)：141-145.

[2] Merris R.Laplacian matrices of graphs：a survey[J].Linear Algebra Appl.,1994(197/198)：143-176.

[3] Cvetkovic D,Rowlinson P,Simic S.Signless Laplacians of finite graphs[J].Linear Algebra Appl.,2007(423)：155-171.

[4] Haemers W,Spence E.Enumeration of cospectral graphs[J].Europ.J.Comb.,2004(25)：199-211.

[5] Fan Y Z,Tam B S,Zhou J.Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs of a given order[J].Linear Multilinear Algebra,2008(56)：381-397.

[6] Desai M,Rao V.acharacterization of the smallest eigenvalue of a graph[J].J.Graph Theory,1994(18)：181-194.

[7] Cvetkovic D,Signless Laplacians and line graphs[J].Bull.Acad.Serbe Sci.Arts,Cl.Sci.Math.Natur.,Sci. Math.,2005(131)：85-92.

[8] Van Dam E R,Haemers W.Which graphs are determined by their spectrum[J].Linear Algebra Appl.,2003(373)：241-272.

[9] Chartrand G,Zhang P.Introduction to graph theory[M].Columbus：McGraw-Hill Companies Inc.,2005.

[10] Feng L H,Li Q,Zhang X D.Minimizing the Laplacian spectral radius of trees with given matching number[J]. Linear Multilinear Algebra,2007(55)：199-207.

[11] Li Q,Feng K Q.On the largest eigenvalue of a graph[J].Acta Math.Appl.Sinica,1979(2)：167-175.

[12] Hong Y,Zhang X D.Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees[J]. Discrete Math.,2005(296)：187-197.

[13] Zhang X D,Luo R.The Laplacian eigenvalues of a mixed graph[J].Linear Algebra Appl.,2003(362)：109-119.

[14] Chen Y.Properties of spectra of graphs and line graphs[J].Appl.Math.J.Chinese Univ.Ser.B,2002(17)：371-376.

O157

A

1672-1454(2011)03-0040-04

2008-06-25;[修改日期]2009-04-16

國家自然科學基金(10601001,60772121);安徽省自然科學基金(070412065);安徽省教育廳自然科學研究項目(2005kj005zd);安徽省青年教師科研資助項目(2008jql021);安徽省高校優秀青年人才基金(2009SQRZ017ZD);安徽大學學術帶頭人科研項目,安徽大學基礎數學創新團隊研究項目