兩種分裂點(diǎn)連接運(yùn)算圖的 Randi′c 譜?

盧志琴，馬小玲

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

0 引言

本文考慮的所有圖均為簡(jiǎn)單且無向的圖. 設(shè)G=(V(G),E(G))是一個(gè)圖, 頂點(diǎn)集為V(G)={v1,v2, ···,vn},邊集為E(G). 圖G的鄰接矩陣記為A(G) = (aij)n×n, 如果vi和vj是鄰接的, 則aij= 1; 否則, aij= 0. 設(shè)di=dG(vi)是G中點(diǎn)vi的度, D(G)=diag(d1,d2,···,dn) 是對(duì)角矩陣. 1975 年, Randi′c提出了Randi′c指標(biāo), 定義為[1]

根據(jù)定義, 圖G的規(guī)范化拉普拉斯矩陣和規(guī)范化無符號(hào)拉普拉斯矩陣分別定義為L(zhǎng)(G)=In?D?1/2(G)A(G)D?1/2(G)和Q(G)=In+D?1/2(G)A(G)D?1/2(G), 其中In為n階單位矩陣. 對(duì)于矩陣Mn×n, 我們用fM(x)表示M的特征多項(xiàng)式, 即fM(x)=det(xIn?M). 因此, fR(G)(x)(fL(G)(x), fQ(G)(x))是Randi′c矩陣(規(guī)范化拉普拉斯矩陣, 規(guī)范化無符號(hào)拉普拉斯矩陣)的特征多項(xiàng)式, 它的根是Randi′c矩陣(規(guī)范化拉普拉斯矩陣, 規(guī)范化無符號(hào)拉普拉斯矩陣)的特征值. 將R(G), L(G)和Q(G)的特征值分別表示為:

注意到δ1(G)=0. 顯然, Randi′c矩陣與規(guī)范化拉普拉斯矩陣和規(guī)范化無符號(hào)拉普拉斯矩陣有直接的聯(lián)系(見文獻(xiàn)[3]): L(G)=In?R(G), Q(G)=In+R(G). 如果γi是R特征值, 則L的特征值δi和Q的特征值ηi分別可以表達(dá)為:

因此，同一個(gè)圖G的L矩陣和Q矩陣的特征值可以被R矩陣的特征值所確定. R(G)(L(G), Q(G))矩陣的特征值及其重?cái)?shù)的集合稱為R-譜(L-譜,Q-譜). 兩個(gè)圖如果有相同的R-譜(L-譜, Q-譜), 則稱其為R同譜(L同譜, Q同譜).

近年來, 一些學(xué)者研究了由圖運(yùn)算構(gòu)造的圖的譜性質(zhì). 在這個(gè)研究方向上有一些著名的圖運(yùn)算, 例如: 不交并、笛卡兒積、Kronocker積、強(qiáng)積、字典積、冠運(yùn)算、邊冠運(yùn)算、鄰接冠等. 這些圖的譜結(jié)果見文獻(xiàn)[4?9]. 兩個(gè)圖的連接運(yùn)算[10]是它們的不交并, 將一個(gè)圖的每個(gè)頂點(diǎn)連接到另一個(gè)圖的每個(gè)頂點(diǎn)上, 并且保持兩個(gè)圖中的原有邊. 一個(gè)圖G的分裂圖[11]記為SP(G), 是將G的每個(gè)點(diǎn)u做一個(gè)拷貝u′, 然后將u′與u的所有鄰點(diǎn)相連而得到的圖. 新增加的點(diǎn)集記為S(G), 即S(G)=V(SP(G))V(G). 現(xiàn)在我們基于分裂圖, 給出以下兩種類型的圖運(yùn)算.

定義1 設(shè)G1和G2是兩個(gè)點(diǎn)不交的圖, 點(diǎn)數(shù)分別為n1和n2. 則

(i) G1和G2的分裂V-點(diǎn)連接圖, 記為G1? G2, 是將SP(G1)中V(G1)的每個(gè)點(diǎn)與G2中的每個(gè)點(diǎn)連接而得到的圖.

(ii) G1和G2的分裂S-點(diǎn)連接圖, 記為G1? G2, 是將SP(G1)中S(G1)的每個(gè)點(diǎn)與G2中的每個(gè)點(diǎn)連接而得到的圖.

注意到如果Gi有ni個(gè)點(diǎn)和mi條邊, i=1,2, 則G1?G2有2n1+n2個(gè)點(diǎn)和3m1+n1n2+m2條邊,G1?G2有2n1+n2個(gè)點(diǎn)和3m1+n1n2+m2條邊.

圖 1 C4和K2的分裂V-點(diǎn)連接圖和分裂S-點(diǎn)連接圖

例 1 設(shè)G1和G2分別為圈C4和完全圖K2. 兩個(gè)圖C4?K2和C4?K2如圖1所示.

1 準(zhǔn)備工作

對(duì)于任意整數(shù)k, n1和n2, Ik記為k階單位矩陣，1k記為k階全1列向量，Jn1×n2是所有項(xiàng)為1的n1×n2階矩陣.

引理 1[12]設(shè)M1, M2, M3, M4分別為p×p, p×q, q×p, q×q矩陣且M1和M4是可逆的. 則

其中M1?M2M?14M3和M4?M3M?11M2分別稱為M4和M1的Schur補(bǔ).

引理2[4]設(shè)A是一個(gè)n×n階實(shí)矩陣, Jn×n為n×n階矩陣, 其所有元素都為1. 則

其中α是一個(gè)實(shí)數(shù), adj(A)是A的伴隨矩陣.

根據(jù)電網(wǎng)絡(luò)理論, Klein和Randi′c[14]提出了一個(gè)名為電阻距離的距離函數(shù). 給定圖G中任意一對(duì)頂點(diǎn)vi和vj,設(shè){i}表示vi和vj之間的電阻距離.

Chen和Zhang[15]證明了電阻距離可以自然地用規(guī)范化拉普拉斯矩陣的特征值和特征向量表示, 并引入了另一個(gè)圖不變量, 定義為Kf?(G)=i

引理 4 設(shè)G為n個(gè)點(diǎn)，m條邊的連通圖, {0=δ1<δ2≤···δn}是G的L(G)的譜, 則

(i)[15]G的度基爾霍夫指數(shù)為

引理3[13]對(duì)任意實(shí)數(shù)c,d>0, 我們有

(ii)[18]G的生成樹數(shù)目τ(G)有下列式子

n×n矩陣M的M-冠[16?17]記為ΓM(x), 被定義為(xIn?M)?1矩陣的所有元素的和, 即:

引理5[19]如果M是一個(gè)n階矩陣且行和等于常數(shù)t

2 分裂V-點(diǎn)連接圖的譜

在這一部分中, 我們得到了兩個(gè)正則圖的分裂V-點(diǎn)連接圖的R-譜, L-譜, Q-譜以及相關(guān)譜的一些應(yīng)用.

設(shè)Gi是ni個(gè)點(diǎn)的ri-正則圖,i=1,2. 根據(jù)定義1(i),G1?G2的點(diǎn)可以由V(G1)∪S(G1)∪V(G2)構(gòu)成,其中V(G1)={v1,v2,···,vn1}, S(G1)={v′1,v′2,···,v′n1}, V(G2)={u1,u2,···,un2}.

顯然, G1?G2的點(diǎn)的度為:

2.1 分裂V-點(diǎn)連接圖的R-譜

G1?G2的鄰接矩陣和對(duì)角矩陣可按V(G1), S(G1)和V(G2)的順序表示為如下塊矩陣形式:

則G1?G2的Randi′c矩陣可表示為:

證明 G1?G2的Randi′c矩陣的特征多項(xiàng)式是

其中

則

因此, 定理1得證.

2.2 分裂V-點(diǎn)連接圖的L(Q)-譜

值得注意的是, 對(duì)于一個(gè)圖G, 有L(G)=I ?R(G), Q(G)=I+R(G). 因此, 圖的規(guī)范化(無符號(hào))拉普拉斯譜可以用圖的Randi′c譜表示. 根據(jù)Randi′c譜與規(guī)范化(無符號(hào))拉普拉斯譜之間的關(guān)系, 以及定理1, 我們得到定理2和3.

定理2 設(shè)Gi是有ni個(gè)點(diǎn)的ri-正則圖，i=1,2. 則G1?G2的規(guī)范化拉普拉斯譜為:

證明 首先, 根據(jù)等式(1)和定理1 (i), 得到了G的規(guī)范化拉普拉斯譜的部分特征值

其中j=2,3···n2.

其次, 根據(jù)定理1 (ii), 我們知道G1?G2的一些Randi′c特征值是方程(2r1+n2)x2?r1γi(G1)x?r1γi(G1)=0的兩個(gè)根, 對(duì)于i=2,3,···,n1. 則G1?G2的規(guī)范化拉普拉斯特征值為方程的兩個(gè)根:

其中γi(i=2,3,···,n1)是R(G1)的特征值. 通過化簡(jiǎn)方程(3), 我們得到

由此得出定理2 (ii)的結(jié)果.

最后, 根據(jù)定理1 (iii), G1?G2的一些規(guī)范化拉普拉斯特征值是方程的三個(gè)根:

通過化簡(jiǎn), 我們得到

故定理2得證.

利用規(guī)范化拉普拉斯特征值與G的度基爾霍夫指數(shù)和生成樹數(shù)目的關(guān)系,我們用G1和G2的Randi′c特征值來考慮G1?G2的度基爾霍夫指數(shù)和生成樹數(shù)目.

推論 1 設(shè)Gi是有ni個(gè)點(diǎn), mi條邊的ri-正則圖, i=1,2. 則G1?G2的度基爾霍夫指數(shù)為:

首先, 應(yīng)用定理2 (i), 得到規(guī)范化拉普拉斯特征值. 因此, 度基爾霍夫指

其中j=2,3,···,n2. 因此

接下來, 通過定理2 (ii), 方程(7)的根β1, β2就是G1?G2的規(guī)范化拉普拉斯特征值.

其中γi(i=2,3,···,n1)為R(G1)的特征值.

因此, 根據(jù)韋達(dá)定理, 我們有

最后, 根據(jù)定理2 (iii), 我們得到δ1(G1?G2)=0. 即有方程

設(shè)方程(9)的另外兩個(gè)根可以表示為x1, x2. 根據(jù)韋達(dá)定理, 我們有

注意到|E(G1?G2)| = 3m1+n1n2+m2. 結(jié)合等式(6), (8)和(10)可以得到G1?G2的度基爾霍夫度指數(shù), 如式(4)所示.

推論 2 設(shè)Gi是有ni個(gè)點(diǎn), mi條邊的ri-正則圖, i=1,2. 則G1?G2的生成樹數(shù)目為:

證明 使用引理4 (ii), 我們知道

為了得到結(jié)果, 我們考慮G1?G2的規(guī)范化拉普拉斯特征值如下:

由方程(7), 我們得到

其中γi(i=2,3,···,n1)為R(G1)的特征值.

由方程(9), 我們得到

通過上述等式(12)和Пni=1di=(2r1+n2)n1rn11(r2+n1)n2, 結(jié)合等式(5), (13)和(14)可以得到G1?G2的生成樹

數(shù)目, 如式(11)所示.

定理3 設(shè)Gi是有ni個(gè)點(diǎn)的ri-正則圖，i=1,2. 則G1?G2的規(guī)范化無符號(hào)拉普拉斯譜為:

證明 定理3 可以很容易地通過定理2 的類似證明得到.

3 分裂S-點(diǎn)連接圖的譜

在這一節(jié)中, 我們主要考慮兩個(gè)正則圖的分裂S-點(diǎn)連接圖的R-譜, L-譜, Q-譜以及一些相關(guān)的應(yīng)用.

設(shè)Gi是ni個(gè)點(diǎn)的ri-正則圖, i = 1,2. 根據(jù)定義1 (ii), G1?G2的點(diǎn)可以由V(G1)∪S(G1)∪V(G2)構(gòu)成, 其中V(G1)={v1,v2,···,vn1}, S(G1)={v′1,v′2,···,v′n1}, V(G2)={u1,u2,···,un2}.

顯然, G1?G2的點(diǎn)的度為:

3.1 分裂S-點(diǎn)連接圖的R-譜

G1?G2的鄰接矩陣和對(duì)角矩陣可按V(G1), S(G1)和V(G2)的順序表示為塊矩陣形式:

則G1?G2的Randi′c矩陣可表示為:

證明 G1?G2的Randi′c矩陣的特征多項(xiàng)式是

其中

則

定理4得證.

3.2 分裂S-點(diǎn)連接圖的L(Q)-譜

在本節(jié)中, 我們應(yīng)用定理4來計(jì)算分裂S-點(diǎn)連接圖的規(guī)范化(無符號(hào))拉普拉斯譜, 以及度基爾霍夫指數(shù)和生成樹的數(shù)目. 通過對(duì)2.2節(jié)中定理和推論的類似證明, 我們可以得到以下主要結(jié)論.

定理 5 設(shè)Gi是有ni個(gè)點(diǎn)的ri-正則圖，i=1,2. 則G1?G2的規(guī)范化拉普拉斯譜為:

推論3 設(shè)Gi是有ni個(gè)點(diǎn), mi條邊的ri-正則圖, i=1,2. 則G1?G2的度基爾霍夫指數(shù)為:

推論4 設(shè)Gi是有ni個(gè)點(diǎn), mi條邊的ri-正則圖, i=1,2. 則G1?G2的生成樹數(shù)目為:

定理6 設(shè)Gi是有ni個(gè)點(diǎn)的ri-正則圖，i=1,2. 則G1?G2的規(guī)范化無符號(hào)拉普拉斯譜為:

4 非正則的Randi′c(規(guī)范化拉普拉斯和規(guī)范化無符號(hào)拉普拉斯)同譜圖

在這一節(jié)中, 我們構(gòu)造了關(guān)于Randi′c矩陣, 規(guī)范化拉普拉斯矩陣和規(guī)范化無符號(hào)拉普拉斯矩陣的幾類非正則同譜圖. 根據(jù)Randi′c矩陣, 規(guī)范化拉普拉斯矩陣和規(guī)范化無符號(hào)拉普拉斯矩陣的定義, 得到引理6.

引理6 如果G1和G2是R-同譜的, 則它們是L-圖譜并且是Q-圖譜的.

觀察1 由上一節(jié)給出的所有定理可知, 所有分裂V-點(diǎn)、分裂S-點(diǎn)連接圖的Randi′c(規(guī)范化拉普拉斯和規(guī)范化無符號(hào)拉普拉斯)譜取決于正則度,頂點(diǎn)數(shù)和圖Gi(i=1,2)對(duì)應(yīng)的譜.此外,我們注意到,盡管G1和G2是正則圖,G1?G2和G1?G2是非正則圖.

定理 7 設(shè)Gi, Hi為ri-正則圖, i = 1,2, 其中G1可以與H1不同. 如果Gi和Hi是R-同譜的, i = 1,2, 則G1?G2和H1?H2是R-同譜, L-同譜并且Q-同譜的; G1?G2和H1?H2也是R-同譜, L-同譜并且Q-同譜的.

證明 根據(jù)引理6和觀察1, 很容易得到定理7.