廣義風(fēng)車(chē)圖的相關(guān)矩陣及指標(biāo)

王雪婷,王 燕

(煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,山東 煙臺(tái) 264005)

文獻(xiàn)[1]定義了距離拉普拉斯矩陣DL(G)=Tr(G)-D(G)和距離無(wú)符號(hào)拉普拉斯矩陣DS(G)=Tr(G)+D(G)。RANDIC在文獻(xiàn)[2]中引入了一個(gè)新的距離矩陣,WANG[3]等重新定義并命名為離心率矩陣ε(G)。ε(G)是由D(G)中保留每一行每一列的最大值,其余元素都為零所構(gòu)成的矩陣,其元素定義為

文獻(xiàn)[4]中定義的風(fēng)車(chē)圖W(η,s)是由η個(gè)完全圖Ks組成,且這η個(gè)Ks的頂點(diǎn)都連接到同一個(gè)節(jié)點(diǎn)。KOOIJ等[5]將風(fēng)車(chē)圖推廣到廣義風(fēng)車(chē)圖,有三種基本的推廣方式。第一種記作W′(η,s),有η個(gè)中心節(jié)點(diǎn),η個(gè)完全圖Ks通過(guò)這η個(gè)中心節(jié)點(diǎn)相連,每個(gè)Ks的頂點(diǎn)都連接到同一個(gè)中心節(jié)點(diǎn),且只與這個(gè)中心節(jié)點(diǎn)相連,而η個(gè)中心節(jié)點(diǎn)構(gòu)成一個(gè)完全圖。第二種記作W″(η,s,l),有l(wèi)個(gè)中心節(jié)點(diǎn),這l個(gè)中心節(jié)點(diǎn)構(gòu)成一個(gè)完全圖,η個(gè)完全圖Ks的頂點(diǎn)都與這l個(gè)頂點(diǎn)相連。第三種記作W″′(η,s,l),有l(wèi)個(gè)中心節(jié)點(diǎn),這l個(gè)中心節(jié)點(diǎn)構(gòu)成獨(dú)立集,η個(gè)完全圖Ks的頂點(diǎn)都與這l個(gè)頂點(diǎn)相連。

本文將計(jì)算廣義風(fēng)車(chē)圖的距離矩陣、離心率矩陣的譜半徑以及相關(guān)指標(biāo),下面是本文用到的定義:

定義6[17]連通圖G的乘法Wiener指標(biāo)定義為π(G)=∏u,v∈V(G)d(u,v)。

本文中,SpecDL(G),SpecDS(G),Specε(G)分別表示DL(G),DS(G)和ε(G)的譜。

1 W′(η,s)的相關(guān)矩陣及指標(biāo)

定理1

其中,α1,α2是方程(α-η+1)(α-3sη+2s+1)-(1-2η)(s-2sη)=0的根;α3,α4是方程α2+(2s+2)α+s+1=0的根。

證明令Pi表示第i行元素全為1,其余元素都為2的η×s階矩陣,In×n,Jn×n分別表示n-級(jí)單位矩陣和n-級(jí)全1矩陣,根據(jù)距離矩陣的定義易得D(W′(η,s))如下:

其中行標(biāo)列標(biāo)均為有序列{u1,u2,u3,…,uη,v11,v12,…,v1s,v21,v22,…,v2s,…,vη1,vη2,…,vηs}。

現(xiàn)對(duì)行列式|αI-D(W′(η,s))|作一些初等變換:

(1)從第η+sη-1行開(kāi)始,依次將第i行乘-1加到第i+1行,其中1≤i≤sη+η,但i?{1,…,η,η+s,η+2s,η+3s,…,η+ηs};

(2)從第η+sη列開(kāi)始,依次將第j列加到第j-1列,其中1≤j≤η+sη,但j?{1,…,η,η+s,η+2s,η+3s,…,η+(η-1)s}。

再將行列式依次按η+ks+2,η+ks+3,…,η+(k+1)s,0≤k≤(η-1)展開(kāi),則有|αI-D(W′(η,s))|=(α+1)(s-1)η|A|。其中,

現(xiàn)將第i行乘-1加到第i+1行,i?{η,2η},再將第j列直接加到第j-1列,j?{η,2η},則可得

現(xiàn)先按照第一列展開(kāi),在展開(kāi)后得到的兩行列式中均再按照第η列展開(kāi),如此可得

|A|=[(α-η+1)(α-3sη+2s+1)-(1-2η)(s-2sη)]|B|,

其中,

綜上可得

|αI-D(W′(η,s))|=(α+1)(s-1)η[(α-η+1)(α-3sη+2s+1)-

(1-2η)(s-2sη)][(α+2s+1)(α+1)-s]η-1。

定理1得證。

根據(jù)定理1中的距離矩陣,可以寫(xiě)出

則DL(W′(η,s))=Tr(W′(η,s))-D(W′(η,s)),DS(W′(η,s))=Tr(W′(η,s))+D(W′(η,s))。

由定理1得定理2和定理3如下:

定理2

其中,β1,β2是方程(β-2sη+s)(β-2η+1)-s(2η-1)2=0的根,β3,β4是方程(β-3sη-2η+1)(β-2sη-η+s)-s=0的根。

定理3

SpecDS(W′(η,s))={3sη-2s+2η-3((s-1)η),γ1,γ2,γ3(η-1),γ4(η-1)},

其中,γ1,γ2是方程(γ-2sη-2η+s+2)(γ-6sη+4s-2η+3)-s(1-2η)2=0的根,γ3,γ4是方程(γ-3sη+4s-2η+3)(γ-2sη-η+s+2)-s=0的根。

定理4

證明令Mi表示第i行元素是0其余元素全為2的η×s階矩陣,所以根據(jù)離心率矩陣的定義,易得

將|δI-ε(W′(η,s))|作如定理1的初等變換,則

定理得證。

定理5在廣義風(fēng)車(chē)圖W′(η,s)中

π(W′(η,s))=4sη(η-1)3s2η(η-1)。

在W′(η,s)中,d(ui,vpq)=2,1≤i≠p≤η,1≤q≤s,則H(W′(η,s),x)的二次項(xiàng)系數(shù)是W′(η,s)中2長(zhǎng)路的條數(shù),即等于sη(η-1)。

根據(jù)以上證明過(guò)程,可以得到

π(W′(η,s))=4sη(η-1)3s2η(η-1)。

在定理5中,當(dāng)λ=1時(shí),可以得到推論1。

WW(W′(η,s))=η(η-1)+sη(6sη+6η-5s-5)。

定理6 在廣義風(fēng)車(chē)圖W′(η,s)中

Sc(W′(η,s),x)=s2η+η(η+s-1)+[sη(s2+s+2η-2)+η(η2-2η+1)]x+

sη(η+2s-1)(η-1)x2+s3η(η-1)x3,

Sc(W′(η,s))=η(η-1)(3s3+4s2+2sη+η-s-1)+sη(s2+s+η-1),

綜上,

Sc(W′(η,s),x)=s2η+η(η+s-1)+[sη(s2+s+2η-2)+η(η2-2η+1)]x+

sη(η+2s-1)(η-1)x2+s3η(η-1)x3。

根據(jù)以上證明過(guò)程,可以得出以下結(jié)論:

Sc(W′(η,s))=η(η-1)(3s3+4s2+2sη+η-s-1)+sη(s2+s+η-1),

2 W″(η,s,l)的相關(guān)矩陣及指標(biāo)

定理7

SpecD(W″(η,s,l))={-1(l-1+(s-1)η),-s-1(η-1),ζ1,ζ2},

其中,ζ1,ζ2是方程ζ2+(s-l-2sη+2)ζ+(1-l)(s+1)+sη(l-2)=0的根。

證明根據(jù)距離矩陣的定義可得

其中行標(biāo)列標(biāo)均為有序列{u1,u2,u3,…,uη,v11,v12,…,v1s,v21,v22,…,v2s,…,vη1,vη2,…,vηs}。

現(xiàn)對(duì)行列式|ζI-D(W″(η,s,l))|作初等變換:

(1)從l+sη-1行開(kāi)始,依次將第i行乘-1加到第i+1行,i?{l,l+s,l+2s,…,l+(η-1)s};

(2)從l+sη列開(kāi)始,依次將第i列加到第i-1列,i?{l+1,l+s+1,l+2s+1,…,l+(η-1)s+1}。

再將由這兩步得到的行列式依次按2,3,…,l,l+ks+2,l+ks+3,…,l+ks,0≤k≤η-1行展開(kāi),則可得到|ζI-D(W″(η,s,l))|=(ζ+1)l-1+(s-1)η|B|,其中,

(ζ+s+1)η-1[ζ2+(s-l-2sη+2)ζ+(1-l)(s+1)+sη(l-2)]。

即

|ζI-D(W″(η,s,l))|=(ζ+1)l-1+(s-1)η(ζ+s+1)η-1[ζ2+(s-l-2sη+2)ζ+(1-l)(s+1)+sη(l-2)]。

定理得證。

根據(jù)定理7中的距離矩陣,可以寫(xiě)出

則

DL(W″(η,s,l))=Tr(W″(η,s,l))-D(W″(η,s,l)),DS(W″(η,s,l))=Tr(W″(η,s,l))+D(W″(η,s,l)),

經(jīng)過(guò)如定理7的計(jì)算過(guò)程,容易得到定理8和9如下:

定理8SpecDL(W″(η,s,l))={0,l+sη,l+s(2η-1)((s-1)η),l+2sη(η-1),l+sη(l-1)}。

定理9SpecDS(W″(η,s,l))={l+sη-2(l-1),l+s(2η-1)-2((s-1)η),l+2s(η-1)-2(η-1),μ1,μ2},其中,μ1,μ2是方程μ2-(5sη+3l-2s-4)μ+(sη+2l-2)(l+2sη-2s-2)+sη(3l+2sη-4)=0的根。

定理10Specε(W″(η,s,l))={-1(l-1),0((s-1)η),-2s(η-1),ξ1,ξ2},其中,ξ1,ξ2是方程ξ2+(2s-2sη-l+1)ξ-2s(l-1)+sη(l-2)=0的根。

證明因?yàn)閑(ui)=1,1≤i≤l,e(vmn)=2,1≤m≤η,1≤n≤s,所以根據(jù)離心率矩陣的定義可以寫(xiě)出

對(duì)|ξI-ε(W″(η,s,l))|作如定理7的初等行列變換,經(jīng)計(jì)算可得

|ξI-ε(W″(η,s,l))|=ξ(s-1)η(ξ+1)l-1(ξ+2s)η-1[ξ2+(2s-2sη-l+1)ξ-2s(l-1)+sη(l-2)]。

定理得證。

定理11 在廣義風(fēng)車(chē)圖W″(η,s,l)中

由以上分析,可以得到:

在定理11中,當(dāng)λ=1時(shí),可以得到推論2。

WW(W′(η,s,l))=sη(3sη+2l-2s-1)+l(l-1)。

定理12 廣義風(fēng)車(chē)圖W″(η,s,l)中

Sc(W″(η,s,l),x)=sη(s+l-1)+l(l+sη-1)+[sη(s-1)(s+l-1)+l(l-1)(sη+l-1)]x+

[slη(sη+s+2l-2)]x+s2η(η-1)(s+l-1)x2,

Sc(W″(η,s,l))=sη(s-1)(s+l-1)+l(l-1)(sη+l-1)+

slη(sη+2l+s-2)+2s2η(η-1)(s+l-1),

s2η(η-1)(s+l-1)2。

證明根據(jù)定理11的證明過(guò)程,當(dāng)頂點(diǎn)a,b間的距離為0時(shí),即a=b,a在W″(η,s,l)中的度有以下兩種情況:(1)度為s-1+l,此時(shí)有sη個(gè)頂點(diǎn);(2)度為sη+l-1,此時(shí)有l(wèi)個(gè)頂點(diǎn).故Sc(W″(η,s,l),x)的常數(shù)項(xiàng)為sη(s+l-1)+l(l+sη-1)。

當(dāng)頂點(diǎn)a,b間的距離為2時(shí),它們?cè)赪″(η,s,l)中的度均為s,所以Sc(W″(η,s,l),x)的二次項(xiàng)系數(shù)為s2η(η-1)(s+l-1)。

綜上,

Sc(W″(η,s,l),x)=sη(s+l-1)+l(l+sη-1)+[sη(s-1)(s+l-1)+l(l-1)(sη+l-1)]x。

根據(jù)上述分析過(guò)程,可得:

Sc(W″(η,s,l))=sη(s-1)(s+l-1)+l(l-1)(sη+l-1)+

slη(sη+2l+s-2)+2s2η(η-1)(s+l-1),

s2η(η-1)(s+l-1)2。

3 W?(η,s,l)的相關(guān)矩陣及指標(biāo)

定理13SpecD(W?(η,s,l))={-2(l-1),-1((s-1)η),-(s+1)(η-1),ρ1,ρ2},其中,ρ1,ρ2是方程ρ2+(s-2l-2sη+3)ρ+sη(3l-4)-2(l-1)(s+1)=0的根。

證明易得

經(jīng)過(guò)計(jì)算易得

|ρI-D(W?(η,s,l)|=

(ρ+2)l-1(ρ+1)(s-1)η(ρ+s+1)(η-1)[ρ2+(s-2sη-2l+3)ρ+sη(3l-4)-2(l-1)(s+1)]。

定理得證。

現(xiàn)根據(jù)D(W?(η,s,l))可以寫(xiě)出對(duì)應(yīng)的

則

DL(W?(η,s,l))=Tr(W?(η,s,l))-D(W?(η,s,l)),

DS(W?(η,s,l))=Tr(W?(η,s,l))+D(W?(η,s,l))。

由定理13的計(jì)算,得到定理14和定理15如下:

定理14SpecDL(W?(η,s,l))={0,l+sη,2l+sη(l-1),2sη+l(η-1),2sη+l-s((s-1)η)}。

定理15SpecDS(W?(η,s,l))={sη+2l-4(l-1),2sη+l-s-2((s-1)η),2sη-2s+l-2(η-1),σ1,σ2},其中,σ1,σ2是方程σ2-(5sη+5l-2s-6)σ+(4l+sη-4)(2sη+l-2s-2)+sη(7l+2sη-8)=0的根。

定理16Specε(W?(η,s,l))={-2(l-1),0((s-1)η),-2s(η-1),2s(η-1),2(l-1)}。

證明顯然e(ui)=2,1≤i≤l,e(vmn)=2,1≤m≤η,1≤n≤s,所以根據(jù)離心率矩陣的定義,有

對(duì)|τI-ε(W?(η,s,l))|進(jìn)行如定理13的初等行和初等列變換,再經(jīng)過(guò)計(jì)算可得

|τI-ε(W?(η,s,l))|=(τ+2)l-1τ(s-1)η(τ+2s)η-1[τ-2s(η-1)][τ-(2l-1)]。

定理17 廣義風(fēng)車(chē)圖W?(η,s,l)中

h(W?(η,s,l),x)=[ηs(s-1)+2slη]x+[s2η(η-1)+sηl(l-1)]x2,

WWλ(W?(η,s,l))=sη(s-1)+2slη+(2λ-1+22λ-1)[s2η(η-1)+sηl(l-1)],

π(W?(η,s,l))=2s2η(η-1)+sηl(l-1)。

同理可得:

h(W?(η,s,l),x)=[ηs(s-1)+2slη]x+[s2η(η-1)+sηl(l-1)]x2,

WWλ(W?(η,s,l))=sη(s-1)+2slη+(2λ-1+22λ-1)[s2η(η-1)+sηl(l-1)],

π(W?(η,s,l))=2s2η(η-1)+sηl(l-1)。

在定理17中,令λ=1,可以得到推論3。

定理18 廣義風(fēng)車(chē)圖W?(η,s,l),

Sc(W?(η,s,l),x)=sη(s+l-1)+slη+[sη(s-1)(s+l-1)+slη(sη+s+l-1)]x+

[s2η(η-1)(s+l-1)+s2η2l(l-1)]x2,

Sc(W?(η,s,l))=sη(s-1)(s+l-1)+slη(sη+s+l-1)+2s2η(η-1)(s+l-1)+2slη(l-1),

證明根據(jù)定理17的證明過(guò)程,當(dāng)頂點(diǎn)a,b間的距離為0時(shí),即a=b,則a要么是Ks中的頂點(diǎn),要么是l個(gè)節(jié)點(diǎn),故Sc(W?(η,s,l),x)的常數(shù)項(xiàng)為sη(s+l-1)+slη。

所以

Sc(W?(η,s,l),x)=sη(s+l-1)+slη+[sη(s-1)(s+l-1)+slη(sη+s+l-1)]x+

[s2η(η-1)(s+l-1)+s2η2l(l-1)]x2。

根據(jù)以上證明過(guò)程,可得:

Sc(W?(η,s,l))=sη(s-1)(s+l-1)+slη(sη+s+l-1)+2s2η(η-1)(s+l-1)+2slη(l-1),