圖的廣義距離特征值

盧鵬麗, 鐘 雨

(蘭州理工大學 計算機與通信學院, 甘肅 蘭州 730050)

本文考慮簡單連通圖,設(shè)圖G=(V(G),E(G))為含有n個頂點的簡單連通圖,其中V(G)={v1,v2,…,vn}表示點集合,E(G)為邊集合.NG(vi)表示頂點vi∈V(G)的鄰居集.頂點vi,vj∈V(G)之間的距離表示為dij(或dvi,vj),則距離矩陣可表示為D(G)=(dij)n×n,其特征值記為μ1≥μ2≥…≥μn.

目前,關(guān)于廣義距離矩陣的研究受到了廣泛關(guān)注[10-15],Roberto[12]得出了圖G經(jīng)過加邊運算后,它的廣義距離譜半徑會變小這一很實用的性質(zhì),研究了廣義距離譜半徑和距離拉普拉斯譜半徑以及距離譜半徑之間的一些不等關(guān)系等.Abdollah[13]等研究了廣義距離矩陣第二大特征值的一些上下界,并驗證了星圖的第二大廣義距離特征值是所有樹中最小的.本文利用最大傳遞度Trmax、最小傳遞度Trmin、距離譜半徑μ1等圖參數(shù)得到了ρ1的一些上下界,并給出了極值情況；研究了ρ2關(guān)于階數(shù)n和直徑d的一個下界；計算了自補圖的廣義距離譜.

1 主要引理

引理1[16]若矩陣A是一個n×n的對稱矩陣,并且其特征值為λ1≥λ2≥…≥λn,則對于所有的x∈Rn(x≠0),有λnxTx≤xTAx≤λ1xTAx.左式成立當且僅當x是A的特征值λn對應(yīng)的特征向量,右式成立當且僅當x是A的特征值λ1對應(yīng)的特征向量.

引理4[19]設(shè)A是一個n階實對稱矩陣,讓其特征值λ1(A)≥λ2(A)≥…≥λn(A).若存在兩個實對稱矩陣N1和N2,使N=N1+N2,則λi(N1)+λ1(N2)≥λi(N)≥λi(N1)+λn(N2),i=1,2,…,n.

2 圖的廣義距離譜半徑

給出n階連通圖G的廣義距離譜半徑的一些界.

定義Hn-1,δ為一個最大度為n-1,第二大度為Δ2,并且Δ2=δ(δ為圖H的最小度)的連通圖.特別的,Hn-1,n-1=Kn.

定理1設(shè)圖G為n階連通圖,則

其中:B=αTri+Trj-(1-α)dij,等式成立當且僅當G?Hn-1,δ或G是一個傳遞正則圖.

證明設(shè)x=(x1,x2,…,xn)T為Dα(G)的特征值ρ1對應(yīng)的特征向量,則

Dα(G)x=ρ1x

(1)

從式(1)的第k項,有

對于vi∈V(G), 由式(1)可得

因此

ρ1xi≥αTrixi+(1-α)Trixj

(2)

同理可得

因此

ρ1xj≥αTrjxj+(1-α)[dijxi+(Trj-dij)xj]

(3)

由式(2)和式(3),可得

(ρ1-αTri)(ρ1-Trj+(1-α)dij)≥(1-α)2dijTri

因此

所以

若定理1等號成立,則式(2)和式(3)中的等號一定成立,即?vk∈V(G),k≠j,xk=xj恒成立.

考慮以下兩種情況：

1)di=n-1.?vj,vk∈NG(vi)(j≠k),可得

因為xj>0,并且xk=xj,所以由上式可得Trj=Trk,即G?Hn-1,δ.

2)di

若xi=xj=xk,則有

ρ1xi=Tr1xi=Tr2xi=…=Trnxi

所以Tr1=Tr2=…=Trn,即G是一個傳遞正則圖.

若xi

因此,Trk=Trl,因為di

ρ1xj=(Trp-2(1-α))xj+2(1-α)xi

因為dip=2,所以?vk∈V(G),使得vi,vp∈NG(vk),對于vi,vp∈NG(vk),可得

(Trp-2(1-α))xj+2(1-α)xi=

(Trk-(1-α))xj+(1-α)xi

移項化簡可得

(1-α)xi=(Trk-Trp+(1-α))xj

因為xi,xj均為正數(shù),若Trk≥Trp,則有xi≥xj,與xi

(1-α)xi=(Trk-Trp+(1-α))xj≤-αxj≤0

與xi>0矛盾.該定理得證.

定理2設(shè)圖G為n階連通圖,則

αTrmin+(1-α)μ1≤ρ1≤αTrmax+(1-α)μ1

其中Trmin≤Tri≤Trmax(1≤i≤n).等式成立當且僅當G是一個傳遞正則圖.

證明設(shè)x=(x1,x2,…,xn)T為Dα(G)的特征值ρ1對應(yīng)的單位特征向量,則

因為

(4)

ρ1≤αTrmax+(1-α)μ1

設(shè)y=(y1,y2,…,yn)T為D(G)的特征值μ1對應(yīng)的單位特征向量,則

由引理1可知:

再次由引理1可得

定理2右邊等式成立當且僅當x既是Dα(G)的特征值ρ1對應(yīng)的單位特征向量,又是D(G)的特征值μ1對應(yīng)的單位特征向量,即

因為xi≥0,所以ρ1=αTri+(1-α)μ1,(1≤i≤n),因此Tr1=Tr2=…=Trn.

同理可得,定理2左邊等式成立當且僅當Tr1=Tr2=…=Trn.該定理得證.

推論1設(shè)圖G為n階連通圖,則

其中Λ=αTrmax+(1-α)μ1,等式成立當且僅當G是傳遞正則圖.

證明由引理2可知：Trmin≤μ1≤Trmax,再結(jié)合引理3和定理2得證.

3 圖的第二大廣義距離特征值

給出了圖的第二大廣義距離特征值的一個基于階數(shù)n和直徑d的下界.

定理3設(shè)圖G為一個直徑為d的n階連通圖,則

其中Ψ=4(1-α)2(d-1)2.

證明設(shè)Pd+1:v1v2…vd+1為圖G中一條直徑路.設(shè)Θ={vi∈V(G)V(Pd+1)|dv1,vi+dvi,vd+1=d},|Θ|=θ,則0≤θ≤n-d-1.

因為dv1,vk+dvd+1,vk≥d,d+2≤k≤n,所以

由引理4可知：

ρ2(G)≥λ2(Dα(G)-Dα(Kn))+ρn(Kn)≥

λ2(B)+ρn(Kn)

所以

因為

是一個關(guān)于x的減函數(shù),所以f(x)≥f(n-d-1).又因為ρn(Kn)=αn-1,所以

該定理得證.

4 自補圖的廣義距離譜

定理4設(shè)圖G為n階r-正則圖,其鄰接矩陣A的譜為{r,λ2,…,λn}.則自補圖H的廣義距離譜為

1)α(8n-2-r)-(1-α)(2+λi),i=2,3,…n,每一個重數(shù)為2；

2)α(5n-1+r)+(1-α)(λi-1),i=2,3,…,n,每一個重數(shù)為2；

其中

證明由自補圖的定義可知H的廣義距離矩陣Dα(H)可表示為

其中:M*=α(8n-2-r)I+(1-α)(2J-2I-A);N*=α(5n-1+r)I+(1-α)(J-I+A);J為全一矩陣;I為單位矩陣.

因為G是r-正則圖,所以A的特征值r所對應(yīng)的特征向量是全一向量1,其余特征向量都與1正交.設(shè)A的特征值λi(i=2,3,…,n)所對應(yīng)的特征向量為Xi,則AXi=λiXi,1TXi=0.

設(shè)ν是矩陣Dα(H)的特征向量ψ對應(yīng)的特征值,根據(jù)Dα(H)ψ=νψ和A1=r1可得

Μ1a+(1-α)nb+2(1-α)nc+3(1-α)nd=νa

(1-α)na+Μ2b+(1-α)nc+2(1-α)nd=νb

2(1-α)na+(1-α)nb+Μ2c+(1-α)nd=νc

3(1-α)na+2(1-α)nb+(1-α)nc+Μ1d=νd

其中:

Μ1=α(8n-2-r)+(1-α)(2n-2-r)

Μ2=α(5n-1+r)+(1-α)(n-1+r)

假設(shè)a=0,帶入上面方程組,化簡得b=c=d=0,矛盾.因此,不失一般性,假設(shè)a=1,求解上面的方程組可得定理中的第(3)和第(4)部分,該定理得證.

推論2設(shè)圖G為n階r-正則圖,其鄰接矩陣A的譜為{r,λ2,…,λn}.則自補圖H的距離拉普拉斯譜為

1)8n-r+λi,i=2,3,…,n,每一個重數(shù)為2；

2)5n+r-λi,i=2,3,…,n,每一個重數(shù)為2；

證明已知Dα(H)-Dβ(H)=(α-β)DL(H),取α=1,β=0,得DL(H)=D1(H)-D0(H),則由定理4可得推論2.

推論3設(shè)圖G為n階r-正則圖,其鄰接矩陣A的譜為{r,λ2,…,λn}.則自補圖H的距離無符號拉普拉斯譜為

1)8n-4-r-λi,i=2,3,…,n,每一個重數(shù)為2；

2)5n-2+r+λi,i=2,3,…,n,每一個重數(shù)為2；