最小Q-特征值第二小的給定懸掛點數(shù)的非二部單圈圖

劉曉蓉,張 榮

(1.青海師范大學(xué) 數(shù)學(xué)系,青海 西寧 810008; 2. 鹽城師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,江蘇 鹽城 224002)

最小Q-特征值第二小的給定懸掛點數(shù)的非二部單圈圖

劉曉蓉1,2,張 榮2

(1.青海師范大學(xué) 數(shù)學(xué)系,青海 西寧 810008; 2. 鹽城師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,江蘇 鹽城 224002)

非二部單圈圖;懸掛點;最小特征值

令G=(V,E)是一個簡單無向圖,它的頂點集V=V(G)={v1,v2,…,vn},邊集E=E(G)。A(G)為圖G的鄰接矩陣,D(G)=diag{d(v1),d(v2),…,d(vn)}為G的度對角矩陣,這里d(vi)是頂點vi的度,稱矩陣Q(G)=D(G)+A(G)為G的擬(無符號)拉普拉斯矩陣(又稱Q-矩陣)。因為D(G)是半正定矩陣,所以它的特征值都為非負(fù)實數(shù),可排列為q1(G)≥q2(G)≥…≥qn(G)≥0,我們稱Q(G)的特征值為圖G的擬拉普拉斯特征值或Q-特征值。

對于一個連通圖來說,它的最小Q-特征值為零當(dāng)且僅當(dāng)它是二部圖。Desai等[1]討論了圖的最小Q-特征值與圖的二部性之間的關(guān)系,建議用最小Q-特征值來衡量一個圖的非二部程度；Fallat等[2]將圖的最小Q-特征值定義為圖的代數(shù)二部度(algebraic bipartiteness)，引入圖的點二部度、邊二部度概念，并建立了與代數(shù)二部度的聯(lián)系；Cardoso等[3]確定了最小Q-特征值達(dá)到最小的n階非二部連通圖為三圈的一個頂點上接出一條路所得到的圖；汪毅等[4]研究了圖的一個偶分支從一個頂點移接到另一個頂點時圖的最小Q-特征值,并證明了最小Q-特征值的一個擾動定理，由此刻畫了在含有某個給定非二部圖作為誘導(dǎo)子圖的連通圖類中最小Q-特征值達(dá)到最小的圖的結(jié)構(gòu)。此后,人們先后對許多非二部連通圖類和非二部單圈圖類確定了最小Q-特征值達(dá)到最小的圖[2，4-11]。

單圈圖是邊數(shù)等于頂點數(shù)加1的簡單連通圖。對于給定階數(shù)和懸掛點數(shù)的非二部單圈圖,范益政等[12]確定了最小Q-特征值達(dá)到最小的圖,本文繼續(xù)研究給定階數(shù)和懸掛點數(shù)的非二部單圈圖,確定了最小Q-特征值達(dá)到第二小的圖。

1 預(yù)備知識

Cn和Pn分別表示階為n的圈和路。令G-u,G-uv,分別表示G中去掉頂點u和去掉邊uv后得到的圖。同樣地,G+uv表示在圖G中增加邊uv?E(G)得到的圖,這里u,v∈V(G)。度為1的頂點稱為圖G的懸掛點,鄰接于懸掛點的頂點稱為G的懸掛鄰點,與懸掛點關(guān)聯(lián)的邊稱為G的懸掛邊。對于v∈V(G),NG(v)定義為圖G中頂點v的所有鄰點組成的集合,我們用dG(u,v)(或d(u,v))表示G中頂點u和v之間的距離,這里u,v∈V(G)。

令x=(x1,x2,…,xn)T∈Rn,那么x可以看成是定義在V(G)上的一個函數(shù),也就是說x是頂點vi到xi=x(vi)的映射。如果x是對應(yīng)于某個Q-特征值的特征向量,那么x(v)可自然地看成是x中對應(yīng)于v的分量。不難看出

(1)

進(jìn)而,對于任意一個單位向量x∈Rn,由對稱矩陣的特征值性質(zhì)知

qn(G)≤xTQ(G)x

等號成立當(dāng)且僅當(dāng)x是對應(yīng)于qn(G)的一個特征向量。

令G1和G2是兩個不相交的圖,v1∈V(G1),v2∈V(G2)。G1和G2的粘合(coalescence)用G1(v1)◇G2(v2)來表示,它是由G1和G2通過重合頂點v1和v2形成一個新的頂點u而得到的圖(詳見文獻(xiàn)[5])。圖G1(v1)◇G2(v2)也可以寫成G1(u)◇G2(u)。如果連通圖G可以表示成G1(u)◇G2(u),這里G1和G2都是非平凡且連通的,那么分別稱G1和G2為圖G的根點為u的一個分支。設(shè)x是定義在G上的向量,H是G的一個分支,如果對應(yīng)于向量x,對任意頂點p∈V(H),都有x(p)=0成立,則稱H是G的對應(yīng)于向量x的零分支;否則稱H為對應(yīng)于向量x的非零分支。

引理1[4]設(shè)G為n階連通圖,它包含以u為根點的二部圖H,如果x=(x1,x2,…,xn)T是G的對應(yīng)于qn(G)的特征向量,則

(i)若x(u)=0,則H是對應(yīng)于x的零分支;

(ii)若x(u)≠0,則對任意的p∈V(H),有x(p)≠0。

引理2[4]設(shè)G是n階非二部連通圖,x是對應(yīng)于qn(G)的特征向量,T是以u為根點對應(yīng)于向量x的非零分支,則|x(q)|<|x(p)|,其中p,q為T的兩個頂點,且q在從u到p的唯一路上。

引理3[9]設(shè)G=G1(v2)◇T(u),G*=G1(v1)◇T(u)為2個n階圖,其中G1是一個包含2個不同頂點v1,v2的非二部連通圖,T是一棵非平凡樹。如果存在對應(yīng)于qn(G)的特征向量x=(x(v1),x(v2),…,x(vn))T,使得|x(v1)|>|x(v2)|或|x(v1)|=|x(v2)|>0,那么qn(G*)

引理4[9]設(shè)G=C(v0)◇B(v0),其中C=v0v1v2…vkukuk-1…u1v0是一個長為2k+1的圈,B是一個階數(shù)為n-2k的偶圖,如圖1所示,那么存在關(guān)于qn(G)的一個特征向量x=(x(v0),x(v1),x(v2),…,x(vk),x(u1),x(u2),…,x(uk),…)T,滿足

(i)|x(v0)|=max{|x(w)||w∈V(C)}>0;

(ii)x(vi)=x(ui),i=1,2,…,k;

(iii)x(vi)x(vi-1)≤0,x(ui)x(ui-1)≤0,i=1,2,…,k。

圖1 C(v0)◇B(v0)Fig.1 C(v0)◇B(v0)

此外,若2k+1

圖Fig.

圖Fig.

2 主要結(jié)果

首先,我們斷言G是圈Cg=v1v2…vgv1的某個頂點上接出一棵非平凡樹得到的，否則,我們假設(shè)G是圈Cg上s(≥2)個不同頂點處接出非平凡樹而得到的。假設(shè)vt是圈Cg上的一個頂點使得|xt|≥|xi|,i=1,2,…,g,則由引理1知,xt≠0，否則,可得x=0,與x為特征向量矛盾。設(shè)vl是圈Cg上的另一頂點,在vl處接出一棵非平凡樹，令

其次,我們斷言g=3,否則,我們假設(shè)g≥5,根據(jù)引理3可知x(g-3)/2=x(g+3)/2。令

令vt是G的一個懸掛點,假設(shè)y=(y1,y2,…,yn)是對應(yīng)于qn(G′)的單位特征向量,根據(jù)引理2,有|y(vt)|>|y(vg)|>0。令

G″=G′-v1vg+v1vt

第五,我們斷言va和vb是相鄰的,否則,我們假設(shè)va和vb是不相鄰的。令vc∈NG(vb)是vb-va上的一個頂點,那么根據(jù)引理2,有|xc|>|xb|。令vt是鄰接于vb的懸掛鄰點,并且

G′=G-vbvt+vcvt

最后,我們斷言d(vb)=3。否則,假設(shè)

d(vb)>3。令vt是鄰接于vb的懸掛鄰點,并且

G′=G-vbvt+vcvt

其次,我們斷言d(v2)=3,否則,假設(shè)

d(v1)≥d(v2)>3。若|x1|<|x2|,則d(v1)>d(v2)>3。在頂點v1處去掉d(v1)-d(v2)懸掛邊，在頂點v2處增加d(v1)-d(v2)懸掛邊，所得到的圖記為G′。根據(jù)引理3可得，qn(G)>qn(G′),但顯然G=G′,產(chǎn)生矛盾，從而|x1|≥|x2|，vs是v2的一個懸掛點。令

G*=G-v2vs+v1vs

[1] Desai M, Rao V. A characterization of the smallest eigenvalue of a graph[J].J. Graph Theory, 1994，18(2):181-194.

[2]FallatS,FanYZ.BipartitenessandtheleasteigenvalueofsignlessLaplacianofgraphs[J].LinearAlgebra&ItsApplications, 2012，436(9):3 254-3 267.

[3]CardosoDM,CvetkovicD,RowlinsonP,etal.AsharplowerboundfortheleasteigenvalueofthesignlessLaplacianofanon-bipartitegraph[J].LinearAlgebra&ItsApplications, 2008,429(11-12):2 770-2 780.

[4]WangY,FanYZ.TheleasteigenvalueofsignlessLaplacianofgraphsunderperturbation[J].LinearAlgebra&ItsApplications,2012,436(7):2 084-2 092.

[5]LimaLSD,OliveiraCS,AbreuNMMD,etal.ThesmallesteigenvalueofthesignlessLaplacian[J].LinearAlgebra&ItsApplications, 2011,435(10):2 570-2 584.

[6]FanYZ,TanYY.TheleasteigenvalueofsignlessLaplacianofnon-bipartitegraphswithgivendominationnumber[J].DiscreteMath, 2014,334(334):20-25.

[7]LiS,WangS.TheleasteigenvalueofthesignlessLaplacianofthecomplementsoftrees[J].LinearAlgebra&ItsApplications, 2012,436(7):2 398-2 405.

[8]LiuR,WanH,YuanJ,etal.TheleasteigenvalueofthesignlessLaplacianofnon-bipartiteunicyclicgraphswithkpendantvertices[J].ElectronJ.LinearAlgebra, 2013,26(2):333-344.

[9]YuGL,GuoSG,XuML.OntheleastsignlessLaplacianeigenvalueofsomegraphs[J].ElectronJ.ofLinearAlgebra,2013,26(8):560-573.

[10]YuG,GuoSG,ZhangR,etal.ThedominationnumberandtheleastQ-eigenvalue[J].AppliedMathematics&Computation,2013,244(2):274-282.

[11]YuGD,FanYZ,WangY.QuadraticformsongraphswithapplicationtominimizingtheleasteigenvalueofsignlessLaplacianoverbicyclegraphs[J].Electron,J.LinearAlgebra, 2014,27(3):213-236.

[12]FanYZ,WangY,GuoH.TheleasteigenvaluesofsignlessLaplacianofnon-bipartitegraphswithpendantvertices[J].DiscreteMath,2012,313(7):903-909.

(責(zé)任編輯：張英健)

The Non-bipartite Unicyclic Graph with Fixed Number of Pendent Vertices Whose Least Q-eigenvalue Attains the Second Smallest

LIU Xiaorong1,2, ZHANG Rong2

(1.Department of Mathematics, Qinghai Normal University, Xining Qinghai 810008, China;2.School of Mathematics and Statistics, Yancheng Teachers University, Yancheng Jiangsu 224002, China)

Non-bipartite unicyclic graph; Pendant vertices; Least eigenvalue

10.16018/j.cnki.cn32-1650/n.201504003

2015-05-20

國家自然科學(xué)基金資助項目(11171290);江蘇省自然科學(xué)基金(BK20151295)

劉曉蓉(1990-)，女，青海同仁人，碩士生，主要研究方向為圖論。

O157.5

A

1671-5322(2015)04-0011-04