廣義邊冠圖的Normalized Laplacian譜

羅艷艷,晏衛(wèi)根

(集美大學(xué)理學(xué)院，福建 廈門 361021)

Hou等[1]定義的圖G和圖H的邊冠圖GH如下:假設(shè)圖G有m條邊e1,e2,…,em,H1,H2,…,Hm為H的m個拷貝,把G的每一條邊ei(1≤i≤m)的兩個端點(diǎn)與Hi中的每個頂點(diǎn)都相連,得到的圖就是GH，進(jìn)而得到了有關(guān)邊冠圖GH的一些譜性質(zhì).Cui等[2]得到了兩個圖的邊冠圖的無符號Laplacian譜.

1　預(yù)備知識

設(shè)A和B分別是m×n和p×q矩陣,定義A和B的張量積(Kronecker積)A?B為如下的mp×nq矩陣:

其中R(G)為G的邊關(guān)聯(lián)矩陣,

廣義邊冠圖的度對角矩陣為

(1)

其中

定義2為了方便書寫,引入如下一個記號:

引理2

(2)

因此

2　主要結(jié)論

定理1設(shè)G是一個有n1個頂點(diǎn)與m條邊的r1-正則圖,H1,H2,…,Hm都是有n2個頂點(diǎn)的r2-正則圖,那么

(n2+2-r2δ-2δ)δj],

其中0=δ1≤δ2≤…≤δn1是圖G的normalized Laplacian特征值.

證明由式(1)和(2)結(jié)合引理1,可得到

det(δ(1+n2)(r2δ+2δ-2)-n2δ(r2+

(n2+2-r2δ-2δ)δj]=

n2)(r2δ+2δ-2)-n2δ(r2+2)+(n2+

2-r2δ-2δ)δj],

定理由此得證.

((r2+2)δj+n2(r2+2)+2(1+n2))2-

(2(r2+2)(1+n2))-1.

由定理1,很容易得到以下推論.

3　應(yīng)　用

上一節(jié)主要得到了有關(guān)廣義邊冠圖的normalized Laplacian譜,作為這一結(jié)果的應(yīng)用,本節(jié)計算廣義邊冠圖的degree-Kirchhoff指標(biāo)和生成樹數(shù)目.

假設(shè)圖G是一個有n個頂點(diǎn)與m條邊的簡單連通圖,它的normalized Laplacian特征值為0=δ1≤δ2≤…≤δn.圖G的degree-Kirchhoff指標(biāo)Kf*(G)由Chen等[4]定義如下:

其中，di與dj表示圖G的頂點(diǎn)i與j的度,rij表示圖G的頂點(diǎn)i和j之間的電阻距離.同時他們證明了對于一個含有n個頂點(diǎn)與m條邊的簡單連通圖,其degree-Kirchhoff指標(biāo)為

其中，δj為圖G的非零normalized Laplacian特征值.關(guān)于計算生成樹數(shù)目的方法有多種,這里主要研究利用圖的normalized Laplacian譜進(jìn)行計算.設(shè)G是一個有n個頂點(diǎn)與m條邊的簡單連通圖,則其生成樹數(shù)目的公式如下[5]

其中,di表示圖G中頂點(diǎn)i的度,δj為圖G的非零normalized Laplacian特征值.

引理3設(shè)K2是兩個頂點(diǎn)的完全圖,H是一個有n2個頂點(diǎn)的r2-正則圖,0=δ1≤δ2≤…≤δn2是圖H的normalized Laplacian特征值,則邊冠圖K2H的degree-Kirchhoff 指標(biāo)是

Kf*(K2H)=(1+n2)(2+r2)+

證明由定理1可知,邊冠圖K2H的norma-lized Laplacian譜是

又有|E(K2則K2H的degree-Kirchhoff 指標(biāo)為

Kf*(K2

由此引理得證.

(m-m2)(1+n2)(r2+2)+

m(r2+2)(n2+1)+

m(r2+2)(n2+1)+

(m-m2)(1+n2)(r2+2)+

定理得證.

利用圖的生成樹的數(shù)目與其Laplacian特征值之間關(guān)系,下面的引理是顯然的.

引理4設(shè)K2是兩個頂點(diǎn)的完全圖,H是一個有n2個頂點(diǎn)的r2-正則圖,0=μ1≤μ2≤…≤μn2是圖H的Laplacian特征值,則邊冠圖K2H的生成樹數(shù)目為

t(K2H)=(n2+2)(μ2+2)(μ3+2)…

(μn2+2).

(1)

證畢.

參考文獻(xiàn)：

[1]HOU Y P,SHIU W C.The spectrum of the edge corona of two graphs[J].Electronic J Linear Alg,2010，20：586-594.

[2]CUI S Y,TIAN G X.The signless Laplacian spectrum of the (edge) corona of two graphs[J].Utilitas Mathematica,2012,88:287-297.

[3]BAPAT R B.Graphs and matrices[M].Berlin:Springer,2010:125-140.

[4]CHEN H Y,ZHANG F J.Resistance distance and the normalized Laplacian spectrum[J].Discrete Appl Math,2007,155:654-661.

[5]FAN C.Spectral graph theory(CBMS regional conference series in mathematics 92)[J].View Issue TOC,1998,30(2):197-199.

[6]LAALI A R F,JAVADI H H S,KIANI D.Spectra of generalized corona of graphs[J].Linear Alg Appl,2016,493:411-425.

[7]HARARY F.Graph theory[J].Advanced Book Program,1969,2(1):67-128.

[8]BIGGS N L.Algebraic graph theory[M].2nd ed.Cambridge:Cambridge University Press,1993:151-181.

[9]LIU Q.The Laplacian spectrum of corona of two graphs[J].Kragujevac J Math,2014,38:163-170.

[10]FRUCHT R,HARARY F.On the corona of two graphs[J].Aequationes Math,1970,4(1/2):322-325.

[11]BARIK S,PATI S,SARMA B K.The spectrum of the corona of two graphs[J].SIAM J Discrete Math,2007,24：47-56.

[12]WANG S L,ZHOU B.The signless Laplacian Spectra of the corona and edge corona of two graphs[J].Linear and Multilinear Algebra,2013,61:197-204.