于 祥,馬小玲

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

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

兩個(gè)圖的點(diǎn)冠運(yùn)算首先由Frucht等[5]引入,其目的是構(gòu)造一類圖,使其自同構(gòu)群是兩個(gè)自同構(gòu)群的織積(wreath product).接著,McLeman等[6]定義了矩陣的一個(gè)新的不變量——M冠,并用它來計(jì)算兩個(gè)圖的點(diǎn)冠運(yùn)算后得到的新圖的鄰接譜,表明了該譜是可以由原來的兩個(gè)圖的譜以及對(duì)應(yīng)圖矩陣的M冠表示.2010年,Hou等[7]給出了圖的邊冠運(yùn)算的定義,并從特征向量的角度得到了兩個(gè)圖的邊冠運(yùn)算后得到的新圖的鄰接譜.2016年,Cui等[8]通過矩陣計(jì)算給出了關(guān)于圖做點(diǎn)冠和邊冠運(yùn)算的新圖的無符號(hào)拉普拉斯譜.2014年,Liu[9]對(duì)兩個(gè)圖的點(diǎn)冠和邊冠運(yùn)算的拉普拉斯譜進(jìn)行了研究.2017年,Chen等[10]研究了兩個(gè)圖做點(diǎn)冠和邊冠運(yùn)算后的新圖的規(guī)范化拉普拉斯譜.近幾年,學(xué)者們將目光轉(zhuǎn)向了兩個(gè)圖的賦權(quán)點(diǎn)冠和賦權(quán)邊冠圖的譜問題研究,Dai等[11]研究了賦權(quán)點(diǎn)冠圖的鄰接譜和拉普拉斯譜.Mahanta等[12]和Liu等[13]則分別給出了賦權(quán)邊冠圖的廣義譜.基于以上理論和結(jié)果,本文采用不同的方法研究了賦權(quán)邊冠圖的鄰接譜、拉普拉斯譜和無符號(hào)拉普拉斯譜,同時(shí),應(yīng)用這些結(jié)果,進(jìn)一步考慮了賦權(quán)邊冠圖的基爾霍夫指標(biāo)和生成樹的個(gè)數(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是一個(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個(gè)頂點(diǎn),m1和m2條邊的兩個(gè)圖.G1和G2的邊冠運(yùn)算定義為G1的每一條邊對(duì)應(yīng)一個(gè)G2,然后將G1的每一條邊的兩個(gè)端點(diǎn)與其對(duì)應(yīng)的G2的每個(gè)頂點(diǎn)相連.G1和G2的邊冠圖G1◇G2有n1+m1n2個(gè)頂點(diǎn).在G1和G2的邊冠運(yùn)算的基礎(chǔ)上,Liu等[13]定義了賦權(quán)邊冠圖,設(shè)圖G1和G2都是簡(jiǎn)單無向圖,G1和G2先做邊冠運(yùn)算得到新圖G1◇G2,然后給新圖中的每條邊都賦一個(gè)加權(quán)因子r,其中0

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

1 準(zhǔn)備工作

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

設(shè)A=(aij)m×n和B=(bij)p×q是兩個(gè)矩陣,則A和B的Kronecker積為一個(gè)mp×nq矩陣A?B,即將A中的每個(gè)元素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是一個(gè)n×n階的矩陣,矩陣M的冠記為ΓM(λ),被定義為矩陣(λIn-M)-1中所有元素的和[5],即

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

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

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

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

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

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

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

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

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

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

(1)

D(G)=

(2)

fA(G)(λ)=

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

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

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

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

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

定理1得證.

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

從圖3(a)計(jì)算可知，隨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肖特基勢(shì)壘降低來解釋；但是隨著MgO厚度的進(jìn)一步增大，Gr/Si電池的串聯(lián)電阻將重新增加.

(iii)rr2,重?cái)?shù)為m1-n1.

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

(3)

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

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

(i) 0,重?cái)?shù)為m1(n2-2);

證明因?yàn)镚2=Kp,q,則由引理3可知

(4)

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

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

L(G)=

(iii) 2r,重?cái)?shù)為m1-n1.

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

因此,對(duì)于實(shí)數(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的廣義拉普拉斯譜的一個(gè)應(yīng)用.

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

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

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

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

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

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

Q(G)=

(7)

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

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

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的廣義無符號(hào)拉普拉斯譜.推論3和4給出了其對(duì)應(yīng)的r權(quán)邊冠圖的無符號(hào)拉普拉斯譜的準(zhǔn)確表達(dá)式.

(iii) 2r(r2+1),重?cái)?shù)為m1-n1.

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

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

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

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

(ii)r(q+2),重?cái)?shù)為m1(p-1);

(iv) 2r和r(n2+2),重?cái)?shù)都是m1-n1.

證明因?yàn)镚2=Kp,q,所以由引理3,可得

(a)r(p+2)的重?cái)?shù)是m1(q-1);

(b)r(q+2)的重?cái)?shù)為m1(p-1);

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

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

A(G)=

利用數(shù)學(xué)軟件MATLAB求解廣義鄰接矩陣A(G),拉普拉斯矩陣L(G)=D(G)-A(G)和無符號(hào)拉普拉斯矩陣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]};

無符號(hào)拉普拉斯譜:

{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的無符號(hào)拉普拉斯譜是σ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é)論對(duì)于考慮r權(quán)邊冠圖的譜是行之有效、并且簡(jiǎn)捷方便的.