盧鵬麗, 鐘 雨

(蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院, 甘肅 蘭州 730050)

本文考慮簡(jiǎn)單連通圖,設(shè)圖G=(V(G),E(G))為含有n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖,其中V(G)={v1,v2,…,vn}表示點(diǎn)集合,E(G)為邊集合.NG(vi)表示頂點(diǎn)vi∈V(G)的鄰居集.頂點(diǎn)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)過(guò)加邊運(yùn)算后,它的廣義距離譜半徑會(huì)變小這一很實(shí)用的性質(zhì),研究了廣義距離譜半徑和距離拉普拉斯譜半徑以及距離譜半徑之間的一些不等關(guān)系等.Abdollah[13]等研究了廣義距離矩陣第二大特征值的一些上下界,并驗(yàn)證了星圖的第二大廣義距離特征值是所有樹(shù)中最小的.本文利用最大傳遞度Trmax、最小傳遞度Trmin、距離譜半徑μ1等圖參數(shù)得到了ρ1的一些上下界,并給出了極值情況；研究了ρ2關(guān)于階數(shù)n和直徑d的一個(gè)下界；計(jì)算了自補(bǔ)圖的廣義距離譜.

1 主要引理

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

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

2 圖的廣義距離譜半徑

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

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

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

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

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

Dα(G)x=ρ1x

(1)

從式(1)的第k項(xiàng),有

對(duì)于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等號(hào)成立,則式(2)和式(3)中的等號(hào)一定成立,即?vk∈V(G),k≠j,xk=xj恒成立.

考慮以下兩種情況：

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

因?yàn)閤j>0,并且xk=xj,所以由上式可得Trj=Trk,即G?Hn-1,δ.

2)di

若xi=xj=xk,則有

ρ1xi=Tr1xi=Tr2xi=…=Trnxi

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

若xi

因此,Trk=Trl,因?yàn)閐i

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

因?yàn)閐ip=2,所以?vk∈V(G),使得vi,vp∈NG(vk),對(duì)于vi,vp∈NG(vk),可得

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

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

移項(xiàng)化簡(jiǎn)可得

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

因?yàn)閤i,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).等式成立當(dāng)且僅當(dāng)G是一個(gè)傳遞正則圖.

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

因?yàn)?/p>

(4)

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

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

由引理1可知:

再次由引理1可得

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

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

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

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

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

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

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

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

定理3設(shè)圖G為一個(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.

因?yàn)閐v1,vk+dvd+1,vk≥d,d+2≤k≤n,所以

由引理4可知：

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

λ2(B)+ρn(Kn)

所以

因?yàn)?/p>

是一個(gè)關(guān)于x的減函數(shù),所以f(x)≥f(n-d-1).又因?yàn)棣裯(Kn)=αn-1,所以

該定理得證.

4 自補(bǔ)圖的廣義距離譜

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

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

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

其中

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

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

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

設(shè)ν是矩陣Dα(H)的特征向量ψ對(duì)應(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,帶入上面方程組,化簡(jiǎn)得b=c=d=0,矛盾.因此,不失一般性,假設(shè)a=1,求解上面的方程組可得定理中的第(3)和第(4)部分,該定理得證.

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

1)8n-r+λi,i=2,3,…,n,每一個(gè)重?cái)?shù)為2；

2)5n+r-λi,i=2,3,…,n,每一個(gè)重?cái)?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}.則自補(bǔ)圖H的距離無(wú)符號(hào)拉普拉斯譜為

1)8n-4-r-λi,i=2,3,…,n,每一個(gè)重?cái)?shù)為2；

2)5n-2+r+λi,i=2,3,…,n,每一個(gè)重?cái)?shù)為2；