广义边冠图的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.