APP下载

广义边冠图的Normalized Laplacian谱

2018-04-11罗艳艳晏卫根

关键词:条边正则数目

罗艳艳,晏卫根

(集美大学理学院,福建 厦门 361021)

Hou等[1]定义的图G和图H的边冠图GH如下:假设图G有m条边e1,e2,…,em,H1,H2,…,Hm为H的m个拷贝,把G的每一条边ei(1≤i≤m)的两个端点与Hi中的每个顶点都相连,得到的图就是GH,进而得到了有关边冠图GH的一些谱性质.Cui等[2]得到了两个图的边冠图的无符号Laplacian谱.

1 预备知识

设A和B分别是m×n和p×q矩阵,定义A和B的张量积(Kronecker积)A⊗B为如下的mp×nq矩阵:

其中R(G)为G的边关联矩阵,

广义边冠图的度对角矩阵为

(1)

其中

定义2为了方便书写,引入如下一个记号:

引理2

(2)

因此

2 主要结论

定理1设G是一个有n1个顶点与m条边的r1-正则图,H1,H2,…,Hm都是有n2个顶点的r2-正则图,那么

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

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

证明由式(1)和(2)结合引理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 应 用

上一节主要得到了有关广义边冠图的normalized Laplacian谱,作为这一结果的应用,本节计算广义边冠图的degree-Kirchhoff指标和生成树数目.

假设图G是一个有n个顶点与m条边的简单连通图,它的normalized Laplacian特征值为0=δ1≤δ2≤…≤δn.图G的degree-Kirchhoff指标Kf*(G)由Chen等[4]定义如下:

其中,di与dj表示图G的顶点i与j的度,rij表示图G的顶点i和j之间的电阻距离.同时他们证明了对于一个含有n个顶点与m条边的简单连通图,其degree-Kirchhoff指标为

其中,δj为图G的非零normalized Laplacian特征值.关于计算生成树数目的方法有多种,这里主要研究利用图的normalized Laplacian谱进行计算.设G是一个有n个顶点与m条边的简单连通图,则其生成树数目的公式如下[5]

其中,di表示图G中顶点i的度,δj为图G的非零normalized Laplacian特征值.

引理3设K2是两个顶点的完全图,H是一个有n2个顶点的r2-正则图,0=δ1≤δ2≤…≤δn2是图H的normalized Laplacian特征值,则边冠图K2H的degree-Kirchhoff 指标是

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

证明由定理1可知,边冠图K2H的norma-lized Laplacian谱是

又有|E(K2则K2H的degree-Kirchhoff 指标为

Kf*(K2

由此引理得证.

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

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

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

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

定理得证.

利用图的生成树的数目与其Laplacian特征值之间关系,下面的引理是显然的.

引理4设K2是两个顶点的完全图,H是一个有n2个顶点的r2-正则图,0=μ1≤μ2≤…≤μn2是图H的Laplacian特征值,则边冠图K2H的生成树数目为

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

(μn2+2).

(1)

证毕.

参考文献:

[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.

猜你喜欢

条边正则数目
J-正则模与J-正则环
移火柴
π-正则半群的全π-正则子半群格
Virtually正则模
任意半环上正则元的广义逆
2018年第2期答案
《哲对宁诺尔》方剂数目统计研究
牧场里的马
认识平面图形
摆三角形的奥秘