劉存磊, 汪 毅, 范益政

(安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院,安徽合肥 230039)

圖的譜半徑與擬懸掛點(diǎn)數(shù)

劉存磊, 汪 毅, 范益政

(安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院,安徽合肥 230039)

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

圖;無符號Laplace矩陣;譜半徑;擬懸掛點(diǎn)

1 引 言

設(shè)G=(V,E)是一個n階簡單圖,其中V={v1,v2,…,vn}為G的頂點(diǎn)集,E={e1,e2,…,em}為G的邊集.圖G的鄰接矩陣定義為A(G)=(aij)n×n,其中,當(dāng)vi,vj鄰接時aij=1,否則aij=0.圖G的不定向關(guān)聯(lián)矩陣定義為M(G)=(mij)n×m,其中當(dāng)vi與ej關(guān)聯(lián)時,mij=1;否則,mij=0.若給G的每條邊指定一個方向,定義Q(G)=(qij)n×m為G的定向關(guān)聯(lián)矩陣,其中當(dāng)vi是ej的起點(diǎn)時,qij=1;當(dāng)vi是ej的終點(diǎn)時,qij=-1;當(dāng)vi與ej不關(guān)聯(lián)時,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的定向關(guān)聯(lián)矩陣.類似地,定義K(G)=M(G)M(G)T為圖G的無符號(不定向,擬)Laplace矩陣(參見[3,4]).不難發(fā)現(xiàn),K(G)=D(G)+A(G).本文僅討論圖的無符號Laplace矩陣.

對于連通圖G,K(G)是一個對稱的,半正定的非負(fù)不可約矩陣.因此,K(G)的特征值均為非負(fù)實(shí)數(shù),可將其排列為λ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))是非負(fù)不可約矩陣,由Perron-Frobenius定理,μ(G)(或ρ(G))是單重的,且對應(yīng)著唯一的(在相差一個常數(shù)的意義下)分量全正的特征向量.習(xí)慣上,分別稱ρ(G)和μ(G)為圖G的鄰接譜半徑和無符號Laplace譜半徑,稱ρ(G)和μ(G)所對應(yīng)的正特征向量為A(G)和K(G)的Perron向量.

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

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

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

研究圖的各種矩陣表示的譜是為了通過譜來刻畫圖的拓?fù)浣Y(jié)構(gòu)性質(zhì).Dam和Haemers[8]比較了階數(shù)不超過11個的所有圖中具有相同鄰接譜和相同無符號Laplace譜的圖各自所占的比例.由比較結(jié)果發(fā)現(xiàn),相對于圖的鄰接譜,無符號Laplace譜能更好地反應(yīng)圖的結(jié)構(gòu)性質(zhì).這也許就是近年來圖的無符號Laplace譜理論研究非常活躍的原因所在.

2 預(yù)備知識

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

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

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

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

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

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

由Courant-Fisher定理,

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

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

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

3 主要結(jié)果

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

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

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

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

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

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

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

證設(shè)G為G(n,0)中具有最小無符號Laplace譜半徑的一個圖.由于G不含擬懸掛點(diǎn),則G不含懸掛點(diǎn),故G不是樹,從而含圈.設(shè)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個擬懸掛點(diǎn)的圖)中,C是唯一具有最小的無符號Laplace譜半徑的圖,其中C是由Cn-1的某個頂點(diǎn)上粘合一條懸掛邊所得.

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

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

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

設(shè)k,l為非負(fù)整數(shù).設(shè)G為連通圖且含邊uv,du＞1,dv＞1.記Gk,l(u,v)是由G在其u,v兩點(diǎn)上分別粘合上路Pk+1和Pl+1所得到的圖.類似地,設(shè)G為連通圖且含非孤立點(diǎn)u,記Gk,l(u)是由G在u點(diǎn)上分別粘合上路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′后的線圖.根據(jù)引理3.7,

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

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

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

圖3.1 擬懸掛點(diǎn)數(shù)為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

國家自然科學(xué)基金(10601001,60772121);安徽省自然科學(xué)基金(070412065);安徽省教育廳自然科學(xué)研究項(xiàng)目(2005kj005zd);安徽省青年教師科研資助項(xiàng)目(2008jql021);安徽省高校優(yōu)秀青年人才基金(2009SQRZ017ZD);安徽大學(xué)學(xué)術(shù)帶頭人科研項(xiàng)目,安徽大學(xué)基礎(chǔ)數(shù)學(xué)創(chuàng)新團(tuán)隊(duì)研究項(xiàng)目