賦權(quán)邊冠圖的廣義譜

于 祥,馬小玲

(新疆大學數(shù)學與系統(tǒng)科學學院,新疆 烏魯木齊 830046)

許多社會、生物和通信系統(tǒng)都可以由網(wǎng)絡(luò)很好地描述,其中頂點代表了系統(tǒng)的元素,邊代表元素之間的相互作用.近年來,對網(wǎng)絡(luò)的研究已經(jīng)成為學者們重點關(guān)注的對象[1].事實上,上面提到的各種網(wǎng)絡(luò)大多是未賦權(quán)的,它們的邊權(quán)重可以看成是單位權(quán)重,但這樣只考慮了頂點的分布和它們之間的關(guān)系,可能忽略了很多頂點之間其他的信息.而賦權(quán)網(wǎng)絡(luò)可以更好地表示現(xiàn)實世界的系統(tǒng),因為權(quán)重在分析某些網(wǎng)絡(luò)屬性時至關(guān)重要.因此,近些年來,關(guān)于構(gòu)造賦權(quán)網(wǎng)絡(luò)的問題在很多領(lǐng)域都有研究,也引起了許多研究人員的關(guān)注[2-4].

兩個圖的點冠運算首先由Frucht等[5]引入,其目的是構(gòu)造一類圖,使其自同構(gòu)群是兩個自同構(gòu)群的織積(wreath product).接著,McLeman等[6]定義了矩陣的一個新的不變量——M冠,并用它來計算兩個圖的點冠運算后得到的新圖的鄰接譜,表明了該譜是可以由原來的兩個圖的譜以及對應圖矩陣的M冠表示.2010年,Hou等[7]給出了圖的邊冠運算的定義,并從特征向量的角度得到了兩個圖的邊冠運算后得到的新圖的鄰接譜.2016年,Cui等[8]通過矩陣計算給出了關(guān)于圖做點冠和邊冠運算的新圖的無符號拉普拉斯譜.2014年,Liu[9]對兩個圖的點冠和邊冠運算的拉普拉斯譜進行了研究.2017年,Chen等[10]研究了兩個圖做點冠和邊冠運算后的新圖的規(guī)范化拉普拉斯譜.近幾年,學者們將目光轉(zhuǎn)向了兩個圖的賦權(quán)點冠和賦權(quán)邊冠圖的譜問題研究,Dai等[11]研究了賦權(quán)點冠圖的鄰接譜和拉普拉斯譜.Mahanta等[12]和Liu等[13]則分別給出了賦權(quán)邊冠圖的廣義譜.基于以上理論和結(jié)果,本文采用不同的方法研究了賦權(quán)邊冠圖的鄰接譜、拉普拉斯譜和無符號拉普拉斯譜,同時,應用這些結(jié)果,進一步考慮了賦權(quán)邊冠圖的基爾霍夫指標和生成樹的個數(shù)問題.

L(G)=D(G)-A(G),Q(G)=D(G)+A(G).

根據(jù)Q(G)和R(G)的定義,很容易可以得到Q(G)=R(G)R(G)T,RT是矩陣R的轉(zhuǎn)置矩陣.特別地,若圖G是一個k-正則圖,則:

L(G)=D(G)-A(G)=kIn-A(G),

Q(G)=D(G)+A(G)=kIn+A(G).

設(shè)G1和G2分別是具有n1和n2個頂點,m1和m2條邊的兩個圖.G1和G2的邊冠運算定義為G1的每一條邊對應一個G2,然后將G1的每一條邊的兩個端點與其對應的G2的每個頂點相連.G1和G2的邊冠圖G1◇G2有n1+m1n2個頂點.在G1和G2的邊冠運算的基礎(chǔ)上,Liu等[13]定義了賦權(quán)邊冠圖,設(shè)圖G1和G2都是簡單無向圖,G1和G2先做邊冠運算得到新圖G1◇G2,然后給新圖中的每條邊都賦一個加權(quán)因子r,其中0

圖1 C4,K3及r權(quán)邊冠圖C4◇K3Fig.1 C4,K3 and r-weighted edge corona graph C4◇K3

1 準備工作

在本節(jié)中介紹一些有用的結(jié)果和概念,這些結(jié)果和概念對得到主要結(jié)論起到了重要作用.本文中,Ik表示k階單位矩陣,1k為k階全1列向量.

設(shè)A=(aij)m×n和B=(bij)p×q是兩個矩陣,則A和B的Kronecker積為一個mp×nq矩陣A?B,即將A中的每個元素aij用aijB代替所得到的矩陣[14].關(guān)于Kronecker積有以下性質(zhì):

(A?B)(C?D)=AC?BD,

(A?B)T=AT?BT,

A?(B+C)=A?B+A?C,

其中,AT是矩陣A的轉(zhuǎn)置矩陣.

引理1[15]設(shè)M1,M2,M3,M4分別是p×p,p×q,q×p,q×q階矩陣.如果M4是可逆矩陣,則

設(shè)M是一個n×n階的矩陣,矩陣M的冠記為ΓM(λ),被定義為矩陣(λIn-M)-1中所有元素的和[5],即

對于函數(shù)ΓM(λ),顯然變量λ出現(xiàn)在其分子和分母中.在這種情況下,稱使分母為零的λ值是該函數(shù)的極點.

引理2[8]如果M是一個n×n階矩陣,并且M的每一行的和都等于常數(shù)s,則

引理3[8]若圖G是一個完全二部圖Kp,q,A(G)為其鄰接矩陣,Q(G)是無符號拉普拉斯矩陣,則

引理4[16]設(shè)G是n個點的連通圖,R(G)是圖G的關(guān)聯(lián)矩陣.若圖G是二部圖,則rank(R(G))=n-1,否則rank(R(G))=n.

引理5[16]設(shè)圖G是譜半徑為ρ的連通圖,-ρ也是G的特征值當且僅當圖G是二部圖.

引理6令G是有n個點的連通圖,設(shè)圖G的拉普拉斯譜為{0=μ1<μ2≤…≤μn},則:

(i) 圖G的基爾霍夫指標為[18]

(ii) 圖G的生成樹的數(shù)目τ(G)[19]為

2 賦權(quán)邊冠圖G=G1◇G2的廣義鄰接譜

對于i=1,2,設(shè)Gi是有ni個點,mi條邊的圖,G1是r1正則圖,A(Gi)是圖Gi的鄰接矩陣,R(Gi)是Gi的關(guān)聯(lián)矩陣.根據(jù)賦權(quán)邊冠圖的定義,對G的頂點集V(G)進行劃分,得到如下互不相交的頂點集V1,U1,U2,…,Um1,使得V=V1∪U1∪U2∪…∪Um1,其中V1是G1的頂點,Ui是圖G1的第i條邊對應的G2的頂點(i=1,2,…,m1).因此,r權(quán)邊冠圖G=G1◇G2的廣義鄰接矩陣和度矩陣如下:

(1)

D(G)=

(2)

fA(G)(λ)=

證明根據(jù)r權(quán)邊冠圖的鄰接矩陣的表達式(1),應用引理1有

fA(G)(λ)=det(λIn1+m1n2-A(G))=

det(Im1?(λIn2-rA(G2)))detB=

應用Kronecker積的性質(zhì),得到以下等式

[Im1?(λIn2-rA(G2))]-1[R(G1)T?1n2]}=

定理1得證.

若G2是正則圖或者完全二部圖時,通過定理1,可以得到r權(quán)邊冠圖G1◇G2的廣義鄰接譜,推論1和2給出了其特征值的準確表達式.

從圖3(a)計算可知，隨MgO厚度增加(0，0.5，1.0，1.5 nm)，器件Rs分別為4.1，3.4，1.8和2.7 Ω/cm2.即隨著MgO厚度的增加，Rs先降低，這可通過MgO介質(zhì)層引起的Al/Si肖特基勢壘降低來解釋；但是隨著MgO厚度的進一步增大，Gr/Si電池的串聯(lián)電阻將重新增加.

(iii)rr2,重數(shù)為m1-n1.

證明因為G2是r2-正則圖,則A(G2)的行和都等于r2.根據(jù)引理2,可得

(3)

其中j=1,2,…,n1.

接下來考慮當G1是正則圖,G2是完全二部圖Kp,q的情況.

(i) 0,重數(shù)為m1(n2-2);

證明因為G2=Kp,q,則由引理3可知

(4)

3 賦權(quán)邊冠圖G=G1◇G2的廣義拉普拉斯譜

設(shè)G1是有n1個點,m1條邊的r1-正則圖,G2是有n2個點,m2條邊的任意圖.令L(G1)和L(G2)分別是圖G1和G2的拉普拉斯矩陣,R(G1)是G1的關(guān)聯(lián)矩陣.因為L(G)=D(G)-A(G),所以由方程(1)和(2),可知r權(quán)邊冠圖G=G1◇G2的廣義拉普拉斯矩陣如下:

L(G)=

(iii) 2r,重數(shù)為m1-n1.

圖2 廣義拉普拉斯矩陣的特征向量的表示Fig.2 Representation of generalized Laplacian eigenvectors

因此,對于實數(shù)pi(i=1,2,…,n1)和a,有

(5)

通過解方程組(5),可得

(6)

設(shè)z1,z2,…,zt是R(G1)z=0的基礎(chǔ)解系,那么有[圖2(c)]

下面給出r權(quán)邊冠圖G=G1◇G2的廣義拉普拉斯譜的一個應用.

(i) 圖G的基爾霍夫指標為

(ii) 圖G的生成樹數(shù)目τ(G)為

由引理6(i)可知,圖G的基爾霍夫指標為

同理,由引理6(ii)可知,圖G的生成樹的數(shù)目為

4 賦權(quán)邊冠圖G=G1◇G2的廣義無符號拉普拉斯譜

設(shè)G1是有n1個點,m1條邊的r1-正則圖,G2是有n2個點,m2條邊的任意圖.令Q(G1)和Q(G2)分別是圖G1和G2的無符號拉普拉斯矩陣,R(G1)是G1的關(guān)聯(lián)矩陣.因為Q(G)=A(G)+D(G),所以根據(jù)方程(1)和(2),有r權(quán)邊冠圖G=G1◇G2的廣義無符號拉普拉斯矩陣為

Q(G)=

(7)

接下來先給出r權(quán)邊冠圖G=G1◇G2的無符號拉普拉斯特征多項式的表達式,如定理4.

證明根據(jù)r權(quán)邊冠圖G的無符號拉普拉斯矩陣的表達式(7),應用Schur補引理1,可知r權(quán)邊冠圖G的無符號拉普拉斯矩陣的特征多項式如下:

fQ(λ)=det(λIn1+m1n2-Q(G))=

det(Im1?((λ-2r)In2-rQ(G2))det(C))=

det(C)=det{(λ-rr1n2)In1-Q(G1)-

rQ(G2))]-1(R(G1)T?1n2)}=

det{(λ-rr1n2)In1-Q(G1)-

因此,定理4得證.

設(shè)G1是正則圖,若G2是正則圖或者完全二部圖,通過定理4,可以得到r權(quán)邊冠圖G1◇G2的廣義無符號拉普拉斯譜.推論3和4給出了其對應的r權(quán)邊冠圖的無符號拉普拉斯譜的準確表達式.

(iii) 2r(r2+1),重數(shù)為m1-n1.

證明因為G2是r2-正則圖,所以G2的無符號拉普拉斯矩陣Q(G2)的行和都等于2r2.因此,由引理2可知

以上得到了Q(G)的m1(n2-1)+2n1個特征值.類似于推論1的證明,其余的m1-n1個特征值是2r(r2+1).

下面考慮G1是正則圖,G2是一個完全二部圖Kp,q的情況.

(i)r(p+2),重數(shù)是m1(q-1);

(ii)r(q+2),重數(shù)為m1(p-1);

(iv) 2r和r(n2+2),重數(shù)都是m1-n1.

證明因為G2=Kp,q,所以由引理3,可得

(a)r(p+2)的重數(shù)是m1(q-1);

(b)r(q+2)的重數(shù)為m1(p-1);

類似于推論2的證明,Q(G)的其余特征值為極點2r和r(n2+2),并且2r和r(n2+2)的重數(shù)都是m1-n1.

圖3 K3,K2及賦權(quán)邊冠圖K3◇K2Fig.3 K3,K2 and weighted edge corona graph K3◇K2

A(G)=

利用數(shù)學軟件MATLAB求解廣義鄰接矩陣A(G),拉普拉斯矩陣L(G)=D(G)-A(G)和無符號拉普拉斯矩陣Q(G)=D(G)+A(G)的特征值,可以得到如下結(jié)論:

圖G的廣義鄰接譜:

{-1.280 8[2],-0.5[3],-0.350 8,0.780 8[2],

2.850 8};

拉普拉斯譜:

{0,0.878 7[2],2[3],3,5.121 3[2]};

無符號拉普拉斯譜:

{1[3],1.550 5,1.634 0[2],3.366 0[2],6.449 5}.

另一方面,已知圖G1和G2的鄰接譜分別為σA(G1)={(-1)[2],2},σA(G2)={-1,1}.通過推論1,有:

G的廣義鄰接譜為{-1.280 8[2],-0.5[3],-0.350 8,0.780 8[2],2.850 8}.

注意到圖G1和G2的拉普拉斯譜分別為σL(G1)={0,3[2]},σL(G2)={0,2}.由定理2可得:

G的廣義拉普拉斯譜為{0,0.878 7[2],2[3],3,5.121 3[2].

已知圖G1和G2的無符號拉普拉斯譜是σQ(G1)={1[2],4},σQ(G2)={0,2},利用推論3有:

σQ(G)={1[3],1.550 5,1.634 0[2],3.366 0[2],6.449 5}.

因此,通過上述例子可以發(fā)現(xiàn),本文主要結(jié)論對于考慮r權(quán)邊冠圖的譜是行之有效、并且簡捷方便的.