賦權邊冠圖的廣義譜

于 祥,馬小玲

(新疆大學數學與系統科學學院,新疆 烏魯木齊 830046)

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

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

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

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

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

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

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

圖1 C4,K3及r權邊冠圖C4◇K3Fig.1 C4,K3 and r-weighted edge corona graph C4◇K3

1 準備工作

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

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

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

(A?B)T=AT?BT,

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

其中,AT是矩陣A的轉置矩陣.

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

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

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

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

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

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

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

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

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

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

2 賦權邊冠圖G=G1◇G2的廣義鄰接譜

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

(1)

D(G)=

(2)

fA(G)(λ)=

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

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

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

應用Kronecker積的性質,得到以下等式

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

定理1得證.

若G2是正則圖或者完全二部圖時,通過定理1,可以得到r權邊冠圖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介質層引起的Al/Si肖特基勢壘降低來解釋；但是隨著MgO厚度的進一步增大，Gr/Si電池的串聯電阻將重新增加.

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

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

(3)

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

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

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

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

(4)

3 賦權邊冠圖G=G1◇G2的廣義拉普拉斯譜

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

L(G)=

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

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

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

(5)

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

(6)

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

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

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

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

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

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

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

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

Q(G)=

(7)

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

證明根據r權邊冠圖G的無符號拉普拉斯矩陣的表達式(7),應用Schur補引理1,可知r權邊冠圖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得證.

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

(iii) 2r(r2+1),重數為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),重數是m1(q-1);

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

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

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

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

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

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

圖3 K3,K2及賦權邊冠圖K3◇K2Fig.3 K3,K2 and weighted edge corona graph K3◇K2

A(G)=

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

圖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}.

因此,通過上述例子可以發現,本文主要結論對于考慮r權邊冠圖的譜是行之有效、并且簡捷方便的.