4度點(diǎn)數(shù)固定的樹的距離譜半徑

,

(上海理工大學(xué) 理學(xué)院,上海 200093)

4度點(diǎn)數(shù)固定的樹的距離譜半徑

汪云,吳寶豐

(上海理工大學(xué) 理學(xué)院,上海200093)

引入了一種圖的變換,得到了距離譜半徑的變化規(guī)律.進(jìn)一步研究了四度點(diǎn)數(shù)固定的樹集,刻畫了該圖類中距離譜半徑最大的極圖.最后,討論了更一般的圖類,即度至少為4的點(diǎn)數(shù)固定的樹集,并確定了極圖.

距離矩陣; 距離譜半徑; 距離Perron向量; 樹

1 基本概念

研究的圖均為連通的簡單無向圖.設(shè)G是n階連通圖,V(G)和E(G)分別是頂點(diǎn)集和邊集.對于任意頂點(diǎn)v∈V(G),用NG(v)表示它的鄰集,并根據(jù)其度數(shù)的奇偶性,稱它為奇度點(diǎn)或偶度點(diǎn).對于圖G的任意2點(diǎn)u,v,用dG(u,v)表示它們的距離,D(G)=(dG(u,v))u,v∈V(G)表示圖G的距離矩陣.顯然,D(G)是實對稱的,所以,它的特征值全為實數(shù).圖G的距離譜半徑用ρ(G)表示,代表D(G)的最大特征值.連通圖對應(yīng)的距離矩陣是不可約的,由Perron-Frobenius定理可知,ρ(G)是單根,且有相應(yīng)的正單位特征向量,記為X(G),稱為G的距離Perron向量.

任取向量X=(x1,…,xn)T∈n(這里X可能是G的距離Perron向量,也可能不是),可將它的分量與G中的點(diǎn)一一對應(yīng),即分量xi對應(yīng)頂點(diǎn)vi,則

若X是D(G)的相應(yīng)于λ的特征向量,則對每一點(diǎn)u∈V(G),有

(1)

稱式(1)為G在u點(diǎn)處的(λ,X)-特征方程.對于任意單位向量X∈n,由Rayleigh-Ritz定理[1],有

ρ(G)≥XTD(G)X

當(dāng)X是G的距離Perron向量時,上式等號成立.對于G的子圖H,記σG(H)為G的距離Perron向量中對應(yīng)于V(H)的所有分量之和.

Pn表示n階路,它是n階連通圖中距離譜半徑最大的圖[2].若一棵樹,將其所有懸掛點(diǎn)刪去后所得圖是一條路,則稱該樹為毛毛蟲圖.顯然,Pn自身也是毛毛蟲圖.

設(shè)V1?V(G),則G-V1表示將圖G刪去V1中的點(diǎn)以及相關(guān)聯(lián)的所有邊后所得到的圖.若V1={u},則用G-u來代替G-{u}.對于E1?E(G),G-E1表示將圖G刪去E1中的邊后所得到的圖.相應(yīng)地,用G-uv來代替G-{uv}.若E′是G的補(bǔ)圖的一些邊的集合,類似地,可以定義G+E′和G+uv.

距離矩陣的定義可以追溯到1841年Cayley 的論文[3],后來Graham[4]于1971年在距離矩陣的負(fù)特征值個數(shù)與數(shù)據(jù)通信系統(tǒng)中的尋址問題之間建立了一種關(guān)系,自此,距離譜的研究引起了眾多圖論學(xué)者的興趣.與鄰接矩陣相比,距離矩陣包含了圖的更多信息,但同時也更加復(fù)雜,任意一條邊的移動或者刪除,都會給距離矩陣帶來很大的變化,所以,研究難度較大.關(guān)于距離譜的綜述見文獻(xiàn)[5].

文獻(xiàn)[6]研究了奇度點(diǎn)數(shù)固定的樹集,刻畫了距離譜半徑最大的極圖.受此啟發(fā),本文研究4度點(diǎn)數(shù)固定的樹集,以及度至少為4的點(diǎn)數(shù)固定的樹集,刻畫了距離譜半徑最大的極圖.

2 關(guān)于圖C(n,a,b)

現(xiàn)引入一類圖C(n,a,b),并得到了一些性質(zhì).在考慮4度點(diǎn)數(shù)固定的樹集時,距離譜半徑最大的圖就是此類圖.

定義1設(shè)b≥a≥0,3(a+b)≤n-2,r=n-3a-3b-2,記圖1所示的圖為C(n,a,b).特別地,C(n,0,0)是路Pn.

圖1 C(n,a,b)Fig.1 C(n,a,b)

定義2設(shè)2≤Δ≤n-1,路Pn-Δ+1的1個端點(diǎn)連接Δ-1個懸掛點(diǎn)所得到的圖記為Bn,Δ,如圖2所示.

圖2 Bn,ΔFig.2 Bn,Δ

引理1[7]設(shè)T是n(n≥4)階樹,Δ為最大度,則ρ(T)≤ρ(Bn,Δ),等式成立當(dāng)且僅當(dāng)T?Bn,Δ.進(jìn)一步,若Δ1>Δ2,則ρ(Bn,Δ1)<ρ(Bn,Δ2).

推論1設(shè)T是n(n≥5)階樹,最大度Δ≥4,則ρ(T)≤ρ(C(n,0,1)),等式成立當(dāng)且僅當(dāng)T?C(n,0,1).

證明因為,Δ≥4,由引理1可知,ρ(T)≤ρ(Bn,Δ)≤ρ(Bn,4)=ρ(C(n,0,1)),等號成立當(dāng)且僅當(dāng)T=C(n,0,1),證畢.

引理3[6]設(shè)T是樹,u∈V(T),NT(u)={u1,…,uk},其中,k≥3,Ti為T-u的包含ui(1≤i≤k)的分支,w∈V(Tk),對于任意t=2,3,…,k-1,令T′=T-{uui:2≤i≤t}+{wui:2≤i≤t}.若σT(Tk)≤σT(T1),則ρ(T′)>ρ(T).

引理4[8]設(shè)G是n階連通圖,X=(x1,x2,…,xn)T是G的距離Perron向量,其分量xi與頂點(diǎn)vi對應(yīng).令vi-1vi,vivi+1是G的2條邊,且vi-1vi,vivi+1中至少有1條是割邊,若xi-1

引理5設(shè)圖C(n,a,b)如圖1所示,b≥a+2≥2, 3(a+b)

a. 0

c. 0

d.xa+1-xa+r+1>xa+2-xa+r>…>xa+s-xa+t+1>0,其中,a+r+1=d-b,a+t+1=a+r+2-s.

圖3 重新編號的C(n,a,b)Fig.3 Renumbered C(n,a,b)

現(xiàn)證明結(jié)論c.

斷言1xp>xq+1.

當(dāng)i=0時,由式(1)可知,

(2)

在假設(shè)條件下,有xp≤xq+1成立.

于是,有yp-j≤yq+1+j(0≤j≤i-1)成立.因此,

即xp-i-xq+1+i≤xp-(i-1)-xq+i≤0,亦即xp-i≤xq+1+i也成立.

由數(shù)學(xué)歸納法可知,對于所有0≤i≤p,均有xp-i≤xq+1+i成立,從而有yp-i≤yq+1+i成立.

斷言2x0>xd.

假設(shè)x0≤xd,現(xiàn)利用數(shù)學(xué)歸納法證xi≤xd-i(0≤i≤p).

當(dāng)i≥1時,設(shè)xj≤xd-j(0≤j≤i-1)已成立.由引理2可知,yj≤yd-j(0≤j≤i-1),因此,

ρ(T)(xi-xd-i)-ρ(T)(xi-1-xd-(i-1))=

于是,xi-xd-i≤xi-1-xd-(i-1)≤0,因此,xi≤xd-i(0≤i≤p).特別地,xp≤xq+1,矛盾,所以,x0>xd,斷言2成立.

在斷言2成立的基礎(chǔ)上,類似地,可用數(shù)學(xué)歸納法得,0

現(xiàn)證明結(jié)論d.

現(xiàn)證明xa+s-i>xa+t+1+i(0≤i≤s-1).

當(dāng)i=0時,

ρ(T)(xa+s-xa+t+1)=

故xa+s>xa+t+1成立.

當(dāng)1≤i≤s-1時,設(shè)xa+s-j>xa+t+1+j(0≤j≤i-1)已成立,即ya+s-j>ya+t+1+j(0≤j≤i-1),則

ρ(T)(xa+s-i-xa+t+1+i)-ρ(T)(xa+s-(i-1)-xa+t+i)=

于是,

xa+s-i-xa+t+1+i>xa+s-(i-1)-xa+t+i>0

(3)

從而xa+s-i>xa+t+1+i成立.由數(shù)學(xué)歸納法可知,對于所有0≤i≤s-1,均有xa+s-i>xa+t+1+i成立.再由式(3)得結(jié)論d成立.

綜上,引理5成立.

定理1設(shè)圖C(n,a,b)如圖1所示,b≥a+2≥2,3(a+b)

ρ(C(n,a+1,b-1))>ρ(C(n,a,b))

設(shè)T1,T2分別是T刪去vb所得的含有點(diǎn)u0,v0的分支,當(dāng)σT(T1)≤σT(T2)時,由引理3可知,結(jié)論顯然成立.當(dāng)σT(T1)>σT(T2)時,ρ(T)·(xvb-xvb-1)=σ(T2)-(σ(T1)+zb)<0,所以,xvb

xvb

(4)

由引理2可知,

所以

從而

(5)

ρ(T′)-ρ(T)≥XT(D(T′)-D(T))X=

其中

現(xiàn)分兩部分來證明w>0.

a. 要證ρ(T′)>ρ(T),只需證w>0.由引理2和引理5的a可得

(6)

于是,由引理5的b及式(4)～(6)可得

r(3a+1)(xvb+r-xva+1)<2w+

因此

(3a+1)r)(xvb+r-xvb)

b. 由引理5的b可知,xvb+r-xvb>0,由Perron-Frobenius定理可知,不可約非負(fù)矩陣的譜半徑大于等于最小行和,故要證w>0,只需證下面的命題.

對于任意0≤j≤a,有

若a≥1,則對于任意1≤j≤a,有

對于任意v∈R,有

對于任意0≤j≤b,有

對于任意1≤j≤b,有

綜上,命題成立,從而ρ(T′)>ρ(T),定理1得證.

3 4度點(diǎn)數(shù)固定的樹

引入一種圖的變換,得到距離譜半徑的變化規(guī)律(引理6).進(jìn)一步,研究4度點(diǎn)數(shù)固定的樹集,以及度至少為4的點(diǎn)數(shù)固定的樹集,刻畫距離譜半徑最大的極圖(定理2和定理3).

圖

因為,G1,G2中至少有1個非平凡分支,不妨設(shè)G1是非平凡分支.選1點(diǎn)v∈V(G1),滿足

于是,

因此,斷言3成立.

斷言4σG(G4)≥σG(G3).

當(dāng)i=1時

所以,xus-1-xus+1<0成立.

當(dāng)2≤i≤s時,設(shè)xus-j-xus+j<0 (1≤j≤i-1)已成立,由引理2可知,ys-j-ys+j<0 (1≤j≤i-1),從而

所以,xus-i-xus+i

由數(shù)學(xué)歸納法可知,對于所有1≤i≤s,均有xus-i-xus+i<0成立.

證明設(shè)T*為滿足引理7所給條件的距離譜半徑最大的毛毛蟲圖,令t為T*中2度點(diǎn)的個數(shù),按下面2種情形討論.

情形1t≤1.

情形2t≥2.

綜上,引理7成立.

證明當(dāng)k=1時,由推論1可知結(jié)論成立.現(xiàn)考慮k≥2的情況,設(shè)T*為T(n,k)中距離譜半徑最大的樹.

斷言5T*的最大偶度等于4.

否則,T*的最大偶度大于或等于6,不妨設(shè)dT*(u)=2t且t≥3.令NT*(u)={u1,…,u2t},Ti為T*-u的含有點(diǎn)ui(1≤i≤2t)的分支.不失一般性,設(shè)σT*(T2t)≤σT*(T1),令v為V(T2t)中的1個懸掛點(diǎn),T=T*-uu2+vu2,T中4度點(diǎn)的個數(shù)仍為k,即T∈T(n,k),但由引理3可知,ρ(T)>ρ(T*),矛盾.

斷言6T*的奇度點(diǎn)均為懸掛點(diǎn).

現(xiàn)通過2種假設(shè)反正斷言6.

a. 假設(shè)T*的最大奇度大于或等于5,不妨設(shè)dT*(u)=2t+1且t≥2.令NT*(u)={u1,…,u2t+1},Ti為T*-u的含有點(diǎn)ui(1≤i≤2t+1)的分支.不失一般性,設(shè)σT*(T2t+1)≤σT*(T1),令v為V(T2t+1)中的1個懸掛點(diǎn),T=T*-{uu2,uu3}+{vu2,vu3},注意到T∈T(n,k),但由引理3可知,ρ(T)>ρ(T*),矛盾.

b. 假設(shè)T*的最大奇度等于3,不妨設(shè)dT*(u)=3.令NT*(u)={u1,u2,u3},Ti為T-u的含有點(diǎn)ui(i=1,2,3)的分支.不失一般性,設(shè)σT*(T3)≤σT*(T1),令v為V(T3)中的1個懸掛點(diǎn),T=T*-uu2+vu2,T中4度點(diǎn)的個數(shù)仍為k,由引理3可知,ρ(T)>ρ(T*),矛盾.

綜合a和b,斷言6成立,從而T*中點(diǎn)的度只有3種情況:1,2或4.

斷言7T*是毛毛蟲圖.

否則,設(shè)T×是將T*中所有懸掛點(diǎn)刪去后所得的圖,則至少存在1個點(diǎn),在圖T×中的度為3或4,將這些點(diǎn)構(gòu)成的集合記為U.對于任意u∈U,仍有dT*(u)=4,令NT*(u)={u1,u2,u3,u4},dT*(ui)≥2,i=1,2,3.再令Ti為T*-u的含有點(diǎn)ui(i=1,2,3,4)的分支,則T*的2度點(diǎn)必全屬于某個V(Ti),i∈{1,2,3,4}.若不然,存在度為2的2個點(diǎn),1個在V(Ti)中,1個在V(Tj)中,i≠j,不妨設(shè)dT*(v1)=dT*(v3)=2,v1∈V(T1),v3∈V(T3),不失一般性,再設(shè)σT*(T3)≤σT*(T1).令T=T*-{uu2,uu4}+{v3u2,v3u4},則T∈T(n,k),但由引理3可知,ρ(T)>ρ(T*),矛盾.故不妨設(shè)T*的2度點(diǎn)全屬于V(T1).

現(xiàn)分2種情形討論.

情形1|UV(T1)|=1.

情形2|UV(T1)|>1.

設(shè)u′為UV(T1)中距離u最遠(yuǎn)的點(diǎn),此時u′可看作情形1中的u,類似地,可推出矛盾.

綜合情形1和2,斷言7成立.

證明當(dāng)k=1時,由推論1可知結(jié)論成立,以下考慮k≥2情況.

設(shè)T*是滿足定理3條件的距離譜半徑最大的樹.假設(shè)Δ(T*)≥5,不妨設(shè)NT*(u)={u1,…,uΔ},令Ti為T*-u的含有點(diǎn)ui(i=1,…,Δ)的分支.不失一般性,設(shè)σT*(TΔ)≤σT*(T1),令T=T*-{uui:2≤i≤Δ-1}+{wui:2≤i≤Δ-1},其中,w為T*的屬于V(TΔ)的懸掛點(diǎn).易知T仍滿足題設(shè)條件,由引理3可知,ρ(T)>ρ(T*),矛盾.所以,T*∈T(n,k),結(jié)合定理2,定理3得證.

[1] HORN R A,JOHNSON C R. Matrix analysis[M].Cambridge:Cambridge University Press,1985.

[3] CAYLEY A.A theorem in the geometry of position[J].The Cambridge Mathematical Journal,1841,2:267-271.

[4] GRAHAM R L, POLLAK H O.On the addressing problem for loop switching[J].Bell System Technical Journal,1971,50(8):2495-2519.

[5] AOUCHICHE M,HANSEN P.Distance spectra of graphs:a survey[J].Linear Algebra and its Applications,2014,458(2):301-386.

[6] LIN H Y,ZHOU B.The distance spectral radius of graphs with given number of odd vertices[J].Electronic Journal of Linear Algebra,2016,31(1):286-305.

[7] WANG Y N,ZHOU B.On distance spectral radius of graphs[J].Linear Algebra and its Applications,2013,438(8):3490-3503.

[8] RUZIEH S N,POWERS D L.The distance spectrum of the pathPnand the first distance eigenvector of connected graphs[J].Linear Multilinear Algebra,1990,28(1/2):75-81.

DistanceSpectralRadiusofTreeswithGivenNumberofVerticesofDegree4

WANG Yun,WUBaofeng

(CollegeofScience,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

A graph transformation was introduced to show the effect of the distance spectral radius.Further,the set of trees with given number of vertices of degree 4 was studied,characterizing the extremal graph with the largest distance spectral radius.Finally,the more general class of graphs,namely,the set of trees with given number of vertices of degree at least 4 was discussed,and also its extremal graph was characterized.

distancematrix;distancespectralradius;distancePerronvector;tree

1007-6735(2017)05-0409-07

10.13255/j.cnki.jusst.2017.05.001

2017-06-03

國家自然科學(xué)基金資助項目(11301340);上海自然科學(xué)基金資助項目(12ZR1420300);滬江基金資助項目(B14005)

汪云(1993-),女,碩士研究生.研究方向:代數(shù)圖論.E-mail:751488437@qq.com

吳寶豐(1978-),男,講師.研究方向:代數(shù)圖論.E-mail:baufern@usst.edu.cn

O157.5

A

(編輯:石 瑛)