卡氏积图的Laplacian 谱半径的上界

周后卿(邵阳学院 理学院， 湖南 邵阳 422000)

卡氏积图的Laplacian 谱半径的上界

周后卿
(邵阳学院 理学院， 湖南 邵阳 422000)

对近年来图的 Laplacian 谱半径上界的研究成果进行了简单梳理. 利用2个图的卡氏积图的特征值,讨论了2个循环图的卡氏积图的 Laplacian 谱半径的上界问题,得到了几个上界,推广了已有文献的结论.

卡氏积图；Laplacian 矩阵；谱半径；上界

图谱理论是图论重要的研究领域之一，在计算机科学、通信网络、信息科学、量子化学以及统计力学中均有广泛应用.利用代数的非负矩阵理论,借助组合数学的一些理论与技巧,研究图谱与图的结构性质,与图的有关不变量(譬如色数、度序列、直径、围长、连通度等)之间的关系.在图谱理论中,为了研究图的性质,常引入一些矩阵,如图的邻接矩阵、Laplacian 矩阵、距离矩阵等,这些矩阵与图的结构密切相关. 通过矩阵论,特别是非负矩阵理论、对称矩阵理论以及组合矩阵论中的经典结论,对图的拓扑结构进行研究;通过图的邻接矩阵或 Laplacian 矩阵表示,建立图的拓扑结构与图的矩阵表示的置换相似不变量之间的联系；同时，将图论中的一些经典结果用于非负矩阵理论和组合矩阵论,从而推动这些理论的发展.

图的拉普拉斯矩阵及其特征值可用于多个领域的研究,并且在物理和化学理论中也有其物理解释.早在19世纪中叶,KIRCHHOFF 就利用 Laplacian 矩阵谱研究了电流网络，并给出了著名的矩阵-树定理. 近几十年来,学者们对图的 Laplacian 谱半径情有独钟,得到了许多深刻的结果.正如 MOHAR[1]所说，Laplacian 特征值比邻接矩阵特征值更能反映图的特质,而且比图的邻接谱更加自然和重要.对图的邻接矩阵和 Laplacian 矩阵特征值而言,最大特征值 (也即图的谱半径)是所有特征值中最重要的一个量.

随着科学技术的进步，新的研究方法不断涌现,借助计算机得到了许多更精确的结果.在网络设计中,循环图网络结构性能好,能长时间稳定运行;实用性强,且具有可靠性、安全性、拓展性等特点,因而,循环图是一类重要的网络拓扑图.借助卡氏积图,可以将网络做大,并且能保持原有的一些特征,这种构造网络的方法行之有效.

在相关文献的基础上,本文着重研究循环图的卡氏积图的Laplacian半径的上界.

1 图的拉普拉斯谱半径的上界

μ1(G)≥μ2(G)≥…≥μn-1(G)≥μn(G)=0.

关于图的Laplacian谱半径上界,学者们研究了一般图,并且讨论了树、单圈图、二部图等特殊图,得到了许多深刻的结果.

(1) ANDERSON等[2]利用相邻2个顶点度给出了其上界：

μ(G)≤max{du+dv：uv∈E},

等式成立当且仅当G是一个正则二部图或半正则二部图.

(2) MERRIS[3]利用平均度改进了上述上界，得到

μ(G)≤max{du+mu：u∈V},

(3) DAS[4]在文献[2]的基础上做了改进,证明了：

设G是一个具有n个顶点的连通图，则

μ(G)≤ max{du+dv-|NG(u)∩NG(v)|：

uv∈E(G)},

其中，NG(u)表示顶点u在G中的邻点集,NG(u)∩NG(v)表示这2个邻点集中的公共顶点数.

(4) LI等[5]在上述文献的基础上,得到

等式成立当且仅当G是一个正则二部图.

(5) SHI[6]利用最大、最小、平均度证明了：

设G是一个具有n个顶点、直径为D、最大度为Δ、最小度为δ、平均度为d的非正则连通图.则

(6) STEVANOVIC[7]证明了具有顶点最大度的树的Laplacian谱半径的一个上界

(7) GUO[8]利用匹配数得到了下列结论：

(8) FENG等[9]讨论了具有给定独立数的单圈图的Laplacian谱半径问题,得到下列结果：

设G是一个具有n(n≥k+4)个顶点、k(k≥1)个悬挂点的单圈图，则μ(G)≤μ(U4,k)等式成立当且仅当G≅U4,k，这里，Ug,k表示顶点为n(n≥k+4)的单圈图，由圈图Cg的一个顶点吸附k条长度几乎相等的路(这些路长度最多相差1)而得到.

文献[9]还得到了下列结论：

(9) GRONE 等[10]获得了以下二部图结果：

设G是一个连通图,则μ(G)≤q(G)等式成立当且仅当G是一个二部图,这里q(G)表示矩阵Q(G)=D(G)+A(G)的最大特征值.

设Βn,m表示所有顶点为n,边为m的二部图，Gm表示在Βn,m中具有最大 Laplacian谱半径的一个二部图.

(10) LI等[11]证明了以下结果：

m≠t(n-t),则μ(Gm)<μ(Gm+1);

(11) PATRA 等[12]得到了以下结论：

设G是一个二部图,G′是由G中的一个顶点邻接另外一个新顶点所得，则μ(G)≤μ(G′).更一般地(见文献[1]),在图G中插入一条新边e，得到另一个图G′,即G′=G+e.则有μ(G)≤μ(G′).

(12) MOHAR[1]证明了下列定理：

设G=G1∪G2是图G的因子分解,则

max(μ(G1),μ(G2))≤μ(G)≤μ(G1)+μ(G2).

(13) 周后卿[13]研究了图在二元运算下,Cartesian 积图的最大Laplacian特征值的上界问题.

(14) 对于具有n个顶点的Halin图G,JIA等[14]证明了其Laplacian谱半径满足不等式：

n-1<μ(G)≤n,

右边不等式成立当且仅当G=Wn，Wn表示有n个顶点的轮图.

(15) LIU等[15]讨论了具有最大Laplacian谱半径的极图问题.

(16) XING等[16]得到了具有固定控制数的Laplacian谱半径，并刻画了其极图.

2 引理、结论及其证明

循环图具有n个顶点的循环图G(n,S)可以定义为循环群上的一个Cayley图,其顶点是循环群Zn上的元素,顶点i,j相连当且仅当j-i是S中的元素,这里S是Zn{0}的一个子集.循环图的矩阵是一个循环矩阵,循环图是一个正则图,每个顶点的度相等.

卡氏积图设G=(V(G),E(G)),H=(V(H),E(H))是2个简单的连通图,那么G与H的卡氏积图G×H是这样的图： 其顶点集为V(G×H)=V(H)×E(H);G×H中任何2个顶点(u,v)与(s,t)相邻当且仅当u=s且v与t在H中相邻；或v=t且u与s在G中相邻，这里u,s∈V(G),v,t∈V(H).

为了证明本文结论，需要下列引理：

引理1[17]设图G与H的顶点分别为n,m,图G与H的Laplacian特征值分别为

μ1(G)≥μ2(G)≥…≥μn-1(G)≥μn(G)=0,

μ1(H)≥μ2(H)≥…≥μn-1(H)≥μn(H)=0，

则G与H的笛卡尔乘积G×H的Laplacian矩阵的特征值为

μi(G)+μj(H)， 1≤i≤n,1≤j≤m.

引理2[18]设G是一个顶点为n(n≥4)的连通、 非完全图.则G的邻接矩阵的最小特征值λmin(G)满足

λmin(G)≥

对于一个γ-正则图G,其Laplacian特征值与其邻接矩阵特征值之间的关系为

μj=γ-λj, 1≤j≤n,

其中,λj为G的邻接矩阵的特征值.

定理1设G与H是2个顶点分别为n,m(n,m≥4), 度分别为s,t的循环图.则G与H的卡氏积图G×H的Laplacian谱半径满足不等式：

其中,Ν,E,O分别表示正整数集、偶数集、奇数集.并且,

证明不妨设Ν,Ε,Ο分别表示正整数集、偶数集、奇数集.

(1) 由引理2可知,

所以,

由引理1,结论得证.

(2) 由引理3,当n∈Ε时,

即

所以有

同理,当m∈Ε时可得

记

由引理1得

μ(G×H)≤s+t+p1+q1.

(3) 当n∈O时，

λmin(G)≥

即

-λmin(G)≤

所以有

同理,当m∈Ο时可得

记

于是,由引理1得

μ(G×H)≤s+t+p2+q2.

(4) 当n∈E,m∈O时，

即

μ(G)≤s+p1,μ(H)≤t+q2.

根据引理1,有

μ(G×H)≤s+t+p1+q2.

(5) 当n∈Ο,m∈Ε时,

即

μ(G)≤s+p2,μ(H)≤t+q1.

由引理1，有

μ(G×H)≤s+t+p2+q1.

定理得证.

定理2设G与H是2个顶点分别为n,m, 度分别为s,t的循环图.则G与H的卡氏积图G×H的Laplacian谱半径

μ(G×H)≤2(s+t)-k-l,

等式成立当且仅当G,H是完全图,其中，

k=|NG(u)∩NG(v)|,uv∈E(G),

l=|NH(u′)∩NH(v′)|,u′v′∈E(H).

证明由

μ(G)≤max{du+dv-|NG(u)∩NG(v)|：uv∈E(G)}

可知,对于循环图G,有

μ(G)≤2du-|NG(u)∩NG(v)|=

2s-|NG(u)∩NG(v)|=2s-k,

这里,|NG(u)∩NG(v)|=k,uv∈E(G).

同理,对于循环图H,有μ(H)≤2t-l,其中,

l=|NH(u′)∩NH(v′)|,u′v′∈E(H).

由引理1,便可推得上述结论.

特别地,当G,H是完全图时，

s=n-1,t=m-1,k=n-2,l=m-2.

因而,有

μ(G×H)=n+m.

例1循环图G=G(15,S1),H=H(20,S2)，

S1={3,5,6,9,10,12},S2={4,5,8,10,12,15,16},分别是度为6,7的正则图.由定理1可得μ(G×H)≤30.5 以及μ(G×H)≤40.2；由定理2得到μ(G×H)≤20.借助计算软件,实际求得

μ(G)=8,μ(H)=9,μ(G×H)=17.

说明定理2的结果准确性更高.

衷心感谢审稿专家给予本文的宝贵意见！

[1] MOHAR B.TheLaplacianSpectrumofGraphs-Graphtheory,CombinatoricsandApplications[M]. New York： John Wiley, 1991.

[2] ANDERSON W N, MORLEY T D. Eigenvalues of the Laplacian of a graph[J].LinearandMultilinearAlgebra,1985, 18： 141-145.

[3] MERRIS R. A note on Laplacian graph eigenvalues[J].LinearAlgebraanditsApplications,1998,285： 33-35.

[4] DAS K. An improved upper bound for Laplacian graph eigenvalues[J].LinearAlgebraanditsApplications. 2003,368 ： 269-278.

[5] LI J S, ZHANG X D. On the Laplacian eigenvalues of a graph [J].LinearAlgebraanditsApplications, 1998,285： 305-307.

[6] SHI L S. The spectral radius of irregular graphs[J].LinearAlgebraanditsApplications, 2009,431： 189-196.

[7] STEVANOVIC D. Bounding the largest eigenvalue of trees in terms of the largest vertex degree[J].LinearAlgebraanditsApplications,2003, 360： 35-42.

[8] GUO J M . On the Laplacian spectral radius of a tree[J].LinearAlgebraanditsApplications,2003, 368： 379-385

[9] FENG L H，YU G H, ILIC A.The Laplacian spectral radius for unicyclic graphs with given independence number[J].LinearAlgebraanditsApplications,2010, 433： 934-944.

[10] GRONE R, MERRIS R, SUNDER V S. The Laplacian spectrum of a graph[J].SIAMJournalonMatrixAnalysisandApplications,1990,11： 218-238.

[11] LI J X, SHIU W C,CHAN W H. On the Laplacian spectral radii of bipartite graphs[J].LinearAlgebraanditsApplications, 2011, 435 ： 2183-2192.

[12] PATRA K L, SAHOO B K, BHUBANESWAR. Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth[J].CzechoslovakMathematicalJournal, 2013,63 (138)： 909-922.

[13] 周后卿.Cartesian积图的最大拉普拉斯特征值[J].邵阳学院学报,2011(1)： 5-7.

ZHOU H Q . The largest eigenvalue of Laplacian matrix of cartesian product graph[J].JournalofShaoyangUniversity, 2011(1)： 5-7.

[14] JIA H C, XUE J. On the Laplacian spectral radii of Halin graphs[J].JournalofInequalitiesandApplications, 2017： 73.

[15] LIU M H, DAS K C,LAI H J.The (signless) Laplacian spectral radii ofc-cyclic graphs withnvertices, girthgandkpendant vertices[J].LinearandMultilinearAlgebra, 2017,65(5)： 869-881.

[16] XING R D,ZHOU B. Laplacian and signless Laplacian spectral radii of graphs with fixed domination number[J].MathematischeNachrichten,2015,288(4)： 476-480.

[17] CVETKOVIC D, DOOB M, SACHS H.SpectraofGraphs,TheoryandApplications[M]. Heidelberg： Johann Ambrosius Barth, 1995.

[18] BELL F K, CVETKOVIC D, ROWLINSON P. Graphs for which the least eigenvalue is minimal[J].LinearAlgebraanditsApplications, 2008, 429： 234-241.

[19] YU G D, FAN Y Z, WANG Y. The least eigenvalue of graphs[J].JournalofMathematicalResearchwithApplications, 2012, 32(6)： 659-665.

ZHOU Houqing
(CollegeofScience,ShaoyangUniversity,Shaoyang422000,HunanProvince,China)

We organize the results of the upper bounds of Laplacian spectral radius for some graphs in the last few years and explore the upper bounds of Laplacian spectral radius for the Cartesian product of circulant graphs based on the eigenvalues of the Cartesian product of two graphs. Our results generalize and improve the conclusion of the existing literatures.

Cartesian product graphs; Laplacian matrix; spectral radius; upper bound

2016-07-25.

国家自然科学基金资助项目(61672356)；湖南省教育厅科学研究项目(2015C1235,2016C1434).

周后卿(1963—)，ORCID： http： //orcid.org/000-0002-9813-1687,男，硕士，教授，主要从事图论及其应用研究， E-mail： zhouhq2004@163.com.

10.3785/j.issn.1008-9497.2018.01.002

O 157.5

A

1008-9497(2018)01-010-04

UpperboundsofLaplacianspectralradiusfortheCartesianproductgraphs.Journal of Zhejiang University (Science Edition)，2018, 45(1)： 010-013