兩類冠圖的Laplacian譜

盧鵬麗，苗玉芳

（蘭州理工大學計算機與通信學院，甘肅蘭州，730050）

兩類冠圖的Laplacian譜

盧鵬麗，苗玉芳

（蘭州理工大學計算機與通信學院，甘肅蘭州，730050）

圖的譜蘊含著圖的許多信息。冠圖是一種比較復(fù)雜的圖，冠圖的譜更加難以計算。文中定義了兩類冠圖，分別是：圖G1和G2的剖分圖的冠點圖G1◇G2和剖分圖的冠邊圖G1☆G2。應(yīng)用分塊矩陣、矩陣的coronal、克羅內(nèi)克積證明了兩類冠圖的Laplacian譜可以表示為原圖G1和G2的Laplacian譜；并給出了兩類冠圖的生成樹數(shù)目以及Kirchhoff指數(shù)。

冠圖；Laplacian矩陣；Laplacian特征多項式；L-譜；生成樹數(shù)目；Kirchhoff指數(shù)

冠圖（corona）最早由R.FRUCHT和F.HARARY提出［1］，是為了解決如下問題：構(gòu)造一些圖，這些圖的自同構(gòu)群可由2個圖的自同構(gòu)群的圈積（wreath product）得到。給定2個頂點不相交的圖G1和G2，將圖G1的每一個頂點對應(yīng)一個圖G2，分別連結(jié)G1的每個頂點和其對應(yīng)的G2中所有頂點所得到的圖稱為G1和G2的冠圖。冠圖的譜計算與帶寬（bandwidth）［2］，最小和（minimum sum）［3］，Ramsey理論的應(yīng)用［4］、可逆圖、生成樹數(shù)目、Kirchhoff指數(shù)等密切相關(guān)。

Kirchhoff指數(shù)和維納指數(shù)一樣，都可以用來描述化學中的分子結(jié)構(gòu)［5?9］。然而卻很難用算法［10?14］實現(xiàn)Kirchhoff指數(shù)的計算，因此給出某類圖的Kirchhoff指數(shù)的界值或給出其公式表示有著重要意義。文獻［15?20］給出了一些冠圖的譜，文獻［21］給出了冠圖的Kirchhoff指數(shù)。

文中定義了兩類冠圖的變體：剖分圖的冠點圖G1◇G2和剖分圖的冠邊圖G1☆G2；證明了兩類冠圖的Laplacian譜可以表示為原圖的Laplacian譜；并給出了兩類冠圖的生成樹數(shù)目以及Kirchhoff指數(shù)。

1 主要引理

在計算Laplacian譜時用到了矩陣的coronal和克羅內(nèi)克積。

引理1［16?17］矩陣Mn×n的M?coronal記為ΓM（x），它的值為矩陣（xIn-M）-1所有元素的和，即

其中，1n為n維元素均為1的列向量。

引理2［17］如果矩陣Mn×n每行元素的和為一個常數(shù)t，那么就有

引理3［21］矩陣A＝（aij）m×n和B＝（bij）p×q的克羅內(nèi)克積A?B是由aijB代替矩陣A中的元素aij得到的mp×nq維的矩陣，即

克羅內(nèi)克積的相關(guān)性質(zhì)有

2）當矩陣AC和BD都存在時有

3）對可逆矩陣A和B有

4）對于矩陣An×n和Bp×p有

引理4［22］令t（G）代表圖G生成樹的個數(shù)。如果G是有n個頂點的連通圖，并且它的Laplacian譜表示為0＝μ1（G）＜μ2（G）≤…≤μn（G），那么有

圖G的Kirchhoff指數(shù)記為Kf（G），被定義為圖G中所有點對之間的阻力距離之和［5，12］。

引理5［14，23］有n個頂點的連通圖G的Kirchhoff指數(shù)的表達式為

式中：μ2（G），…，μn（G）是圖G的非零Laplacian特征值。

2 剖分圖的冠點圖的譜

下面給出剖分圖的冠點圖的定義。剖分圖的冠點圖是指：給定2個頂點不相交的圖G1和G2，將圖G1的每一個頂點對應(yīng)圖G2的一個剖分圖的拷貝，分別連結(jié)G1的每個頂點和其對應(yīng)的G2的剖分圖中所有原G2的頂點，所得到的圖記為G1◇G2。

假設(shè)圖G1是有n1個頂點m1條邊的任意圖，G2是有n2個頂點m2條邊的任意圖，那么G1◇G2有n1（1+ n2+m2）個頂點，m1+n1n2+2n1m2條邊。

圖G的剖分圖S（G）是通過在G的每條邊插入一個新的頂點得到的。為了將矩陣分塊表示，下面給出剖分圖的冠點圖的頂點編號。設(shè)圖G和圖H都是簡單有限圖，分別有n1和n2個頂點，剖分圖的冠點圖由一個G和n1個S（H）組成。圖G的頂點編號為{v1，v2，…，vn1}，n1個S（H）中原圖H中的頂點記為H1，H2，…，Hn1，而n1個剖分圖S（H）中新插入的頂點集記為E（H1），E（H2），…，E（Hn1）。假設(shè)H1的頂點編號為{h1，h2，…，hn2}，那么Hi的第k個頂點hk的編號為n1k+i。若E（H1）的頂點編號為{e1，e2，…，em2}，那么E（Hi）的第k個頂點的編號為（n2+k）n1+i。圖1給出剖分圖的冠點圖的示例圖。

下面給出G1◇G2的頂點度：

圖1 剖分圖的冠點圖Fig.1 Corona?vertex of the subdivision graph

定理1 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，對剖分圖的冠點圖有

證明 設(shè)L1表示G1的Laplacian矩陣，R2表示G2的關(guān)聯(lián)矩陣；由G2是r2正則圖，得圖G2的度矩陣為D2；那么G1◇G2的Laplacian矩陣L為

由此可得G1◇G2的Laplacian特征多項式

因此，得證。

推論1 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，剖分圖的冠點圖G1◇G2的L?譜為：1）根為2，重數(shù)為n1m2-n1n2；2）對每個μi（G2），（i＝2，3，…，n2），方程x2-（3+r2）x+2+ μi（G2）＝0的2個根，每個根的重數(shù)為n1；3）對每個μi（G1）（i＝1，2，…，n1），方程（x3-（3+r2+n2+ μi（G1））x2+（2+2n2+r2n2+3μi（G1）+r2μi（G1））x-2μi（G1））的3個根。

定理2 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，得G1◇G2的生成樹個數(shù)為

定理3 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，有Kirchhoff指數(shù)：

3 剖分圖的冠邊圖的譜

下面給出剖分圖的冠邊圖的定義。剖分圖的冠邊圖是指：給定2個頂點不相交的圖G1和G2，將圖G1的每一個頂點對應(yīng)圖G2的一個剖分圖，分別連結(jié)G1的每個頂點和其對應(yīng)的G2的剖分圖中所有新插入的頂點，所得到的圖記為G1☆G2。

假設(shè)圖G1是有n1個頂點m1條邊的任意圖，G2是有n2個頂點m2條邊的任意圖，那么G1☆G2有n1（1+n2+m2）個頂點m1+3n1m2條邊。G1☆G2和G1◇G2有相同的頂點編號，圖2為剖分圖的冠邊圖的示例圖。

下面給出G1☆G2的頂點度：

圖2 剖分圖的冠邊圖Fig.2 Corona?edge of the subdivision graph

定理4 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，對剖分圖的冠邊圖有

證明 設(shè)L1表示G1的Laplacian矩陣，R2表示G2的關(guān)聯(lián)矩陣；由G2是r2正則圖，得G2的度矩陣D2＝那么G1☆G2的Laplacian矩陣L為

由此可得G1☆G2的Laplacian特征多項式

因此，得證。

推論2 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，得剖分圖的冠邊圖G1☆G2的L?譜為：1）根為3，重數(shù)為n1（m2-n2-1）；2）對每個μi（G2）（i＝2，…，n2），有方程x2-（3+r2）x+2+ μi（G2）＝0的2個根，每個根的重數(shù)為n1；3）對每個μi（G1）（i＝1，2，…，n1），有方程x4-（6+r2+m2+ μi（G1））x3+（9+6μi（G1）+5m2+4r2+ r2m2+r2μi（G1））x2-（9m2+9μi（G1）+4r2μi（G1）+ 3r2m2+3r2-3m2）x+2r2m2-n2r22＝0的4個根。

定理5 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，有

定理6 設(shè)G1是有n1個頂點的任意圖，G2是有n2個頂點m2條邊的r2正則圖，有Kirchhoff指數(shù)：

4 結(jié)論

文中定義了兩類新的冠圖，剖分圖的冠點圖G1◇G2和剖分圖的冠邊圖G1☆G2。計算了當G1為任意圖，G2為正則圖時兩類冠圖的Laplacian譜；證明了兩類冠圖的生成樹數(shù)目及Kirchhoff指數(shù)可以由原圖的Laplacian譜表示。

［1］FRUCHT R，HARARY F.On the corona of two graphs［J］.Aequationes Mathematicae，1970，4（3）：322?325.

［2］CHINN P Z，YUAN J.The bandwidth of the corona of two graphs［J］.Congressus Numerantium，1992：141?141.

［3］WILLIAMS K.On the minimum sum of the corona of two graphs［J］.Congressus Numerantium，1993：43?43.

［4］NENOV N.Application of the corona?product of two graphs in Ramsey theory［J］.Annuaire Univ Sofia Fac Math Inform，1985，79（1）：349?355.

［5］BONCHEV D，BALABAN A T，LIU X，et al.Molecular cy? clicity and centricity of polycyclic graphs.I.Cyclicity based on resistance distances or reciprocal distances［J］.Interna?tional Journal of Quantum Chemistry，1994，50（1）：1?20.

［6］DAS K C，GUNGOR A D，CEVIK A S.On Kirchhoff index and resistance?distance energy of a graph［J］.Match?Com?munications inMathematicalandComputerChemistry，2012，67（2）：541.

［7］ESTRADA E，HATANO N.Topological atomic displace?ments，Kirchhoff and Wiener indices of molecules［J］.Chemical Physics Letters，2010，486（4）：166?170.

［8］XIAO W J，GUTMAN I.Resistance distance and Laplacian spectrum［J］.Theoretical Chemistry Accounts，2003，110（4）：284?289.

［9］ZHOU B，TRINAJSTIC N.A note on Kirchhoff index［J］.Chemical Physics Letters，2008，455（1）：120?123.

［10］BABIC D，KLEIN D J，LUKOVITS I，et al.Resistance distance matrix：a computational algorithm and its applica?tion［J］.International Journal of Quantum Chemistry，2002，90（1）：166?176.

［11］BAPAT R B，GUTMAN I，XIAO W J.A simple method for computing resistance distance［J］.Zeitschrift fur Naturfors?chung A，2003，58（9／10）：494?498.

［12］KLEIN D J，RANDIC M.Resistance distance［J］.Journal of Mathematical Chemistry，1993，12（1）：81?95.

［13］PALACIOS J L.Resistance distance in graphs and random walks［J］.International Journal of Quantum Chemistry，2001，81（1）：29?33.

［14］ZHU H Y，KLEIN D J，LUKOVITS I.Extensions of the Wiener number［J］.Journal of Chemical Information and Computer Sciences，1996，36（3）：420?428.

［15］BARIK S，PATI S，SARMA B K.The spectrum of the co?rona of two graphs［J］.SIAM Journal on Discrete Mathe?matics，2007，21（1）：47?56.

［16］MCLEMAN C，MCNICHOLAS E.Spectra of coronae［J］.Linear Algebra and its Applications，2011，435（5）：998?1007.

［17］CUI S Y，TIAN G X.The spectrum and the signless Lapla?cian spectrum of coronae［J］.Linear Algebra and its Appli?cations，2012，437（7）：1692?1703.

［18］HOU Y P，SHIU W C.The spectrum of the edge corona of two graphs［J］.Electron J Linear Algebra，2010，20（58）：6?594.

［19］WANG S L，ZHOU B.The signless Laplacian spectra of the corona and edge corona of two graphs［J］.Linear and Mul?tilinear Algebra，2013，61（2）：197?204.

［20］LIU X G，LU P L.Spectra of subdivision?vertex and subdi?vision?edge neighbourhood coronae［J］.Linear Algebra and its Applications，2013，438（8）：3547?3559.

［21］JOHNSON C R，HORN R A.Topics in matrix analysis［M］.Cambridge：Cambridge University，1991：411?426.

［22］CVETKOVIC D M，DOOB M，SACHS H.Spectra of graphs：theory and application［M］.New York：Academic Press，1980：375?386.

［23］GUTMAN I，MOHAR B.The Quasi?Wiener and the Kirch?hoff indices coincide［J］.Journal of Chemical Information and Computer Sciences，1996，36（5）：982?985.

［24］ZHANG F Z.The Schur complement and its applications［M］.［S.l.］：Springer，2006：120.

Laplacian spectrum of two classes of corona graphs

LU Pengli，MIAO Yufang
（School of Computer and Communication，Lanzhou University of Technology，Lanzhou 730050，China）

The spectra contain a lot of information concerning a graph.The corona graphs are complex and the com?putation of their spectra is more complex.In this paper，two classes of corona graphs were defined：the corona?ver?tex of the subdivisional graph of G1and G2，denoted by G1◇G2，and the corona?edge of the subdivisional graph of G1and G2，denoted by G1☆G2.Using the block matrix，the coronal and Kronecker product，the Laplacian spectra of G1◇G2and G1☆G2were determined in terms of the corresponding spectra of G1and G2.By using the Laplacian spectra，the number of spanning trees and Kirchhoff index of G1◇G2and G1☆G2are also obtained.

corona graph；Laplacian matrix；Laplacian characteristic polynomial；L?spectrum；spanning trees；Kirchhoff index

10.3969／j.issn.1006?7043.201308055

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1006?7043.201308055.html

O157.5，O157.6

A

1006?7043（2015）02?0196?04

2013?08?28.網(wǎng)絡(luò)出版時間：2014?11?27.基金項目：國家自然科學基金資助項目（11361033）.

盧鵬麗（1973?），女，教授，碩士生導(dǎo)師.

盧鵬麗，E?mail：lupengli88＠163.com.