两类双圈图的Laplacian谱确定问题

王展青，王力工*，梅若星，翟若男，董占鹏

（西北工业大学　理学院应用数学系，陕西西安710072）



两类双圈图的Laplacian谱确定问题

王展青，王力工*，梅若星，翟若男，董占鹏

（西北工业大学理学院应用数学系，陕西西安710072）

设G =（V（G），E（G））是一个简单连通图，V（G），E（G）分别表示图G的顶点集和边集.如果与图G同Laplacian谱的图都与G同构，则称图G由它的Laplacian谱确定.该文定义了两类双圈图Q（n；n1，n2，···，nt）和B（n；n1，n2），证明了双圈图Q（n；n1），Q（n；n1，n2），Q（n；n1，n2，n3）和双圈图B（n；n1，n2）分别由它们的Laplacian谱确定.

Laplacian矩阵；Laplacian特征多项式；Laplacian谱

§1　引　言

本文所考虑的图都是简单连通无向图.双圈图是指一个边数比顶点数多1的简单连通图.根据一个n阶双圈图的双圈相对位置的不同，可以将n阶双圈图划分为三类，分别为An（p，q），Bn，m（p，q）和Cn（p，q），其中:An（p，q）表示其中两个圈Cp和Cq有且只有一个公共顶点的n阶双圈图，Bn，m（p，q）表示其中两个圈Cp和Cq有m（≥2）个公共顶点的n阶双圈图，Cn（p，q）表示其中两个圈Cp和Cq没有公共顶点的n阶双圈图.设图G =（V（G），E（G））的顶点集和边集分别为V（G）= ｛v1，v2，···，vn｝和E（G）.用A（G）表示图G的邻接矩阵，di= di（G）= dG（vi）表示顶点vi的度，D（G）= diag（d1，d2，···，dn）表示顶点度对角矩阵. deg（G）=（d1，d2，···，dn）表示图G的顶点度序列，当顶点度序列中有k个相等的di时，可将这k个di记为dki.矩阵L（G）= D（G）- A（G）为图G的Laplacian矩阵.多项式ϕ（L（G）；µ）= det（µIn- L（G））= l0µn+ l1µn-1+···+ ln表示图G的Laplacian特征多项式，In是一个n×n阶单位矩阵.下文将ϕ（L（G）；µ）写成ϕ（G；µ）或直接写成ϕ（G）.设µ1≥µ2≥···≥µn是L（G）的特征值，它们构成了图G的Laplacian谱.如果两个图有相同的Laplacian谱，就说它们是Laplacian同谱图.如果与图G同Laplacian谱的图都与图G同构，则称图G可由它的Laplacian谱确定.

“哪些图可由它们的谱确定？”这一典型问题是由G¨unthard和Primas于1956年提出的［1］，它起源于化学，是图谱理论中一个有趣且困难的问题. 1966年，Fisher在考虑Kac［2］提出的问题“一个人能否听到鼓声的形状”时，研究的正是图的谱确定问题.研究这个问题的另一动机来自于复杂性理论. 2003年，van Dam和Haemers再次提出这个问题［3］，并受到国内外学者的广泛关注.寻找具有特殊结构的图的邻接谱，Laplacian谱或signless Laplacian谱确定问题是一件非常有意义的事情.这方面好的研究成果见综述［3-4］和文献［5-6］.

本文定义了图Q（n；n1，n2，···，nt），图B（n；n1，n2）和图G4，见图1所示.然后证明了双圈图Q（n；n1），Q（n；n1，n2），Q（n；n1，n2，n3）和双圈图B（n；n1，n2）分别由它们的Laplacian谱确定.

图1　图Q（n；n1，n2，···，nt），　图B（n；n1，n2），　图G4～= K4- e

§2　基本引理

引理2.1［3］对于图G，由其Laplacian谱可以确定图G的:

（1）顶点数.

（2）边数.

（3）分支数数目.

（4）顶点度的平方和.

（5）生成树的个数.

引理2.2［7-8］设图G的顶点集和边集分别为V（G）/=∅和E（G）/=∅.则有

其中∆是图G的最大的顶点度，mi表示图G中与顶点vi邻接的顶点的度数的平均值.

引理2.3［9］多项式ϕ（G）的系数li可由下式得出:

其中Φ表示恰有i个连通分支的生成森林，它的每个分支都是一棵树，用p（Φ）表示森林Φ中各个分支的顶点数的乘积.

引理2.4［5］图G有n个顶点，m条边，deg（G）=（d1，d2，···，dn）为其非递增的顶点度序列. 则ϕ（L（G）；µ）的前四个系数为

式中nG（C3）表示图G中三角形的数目.

设Pn和Cn分别是具有n个顶点的路和圈，Bn是从L（Pn+1）中删除路Pn+1的两个端点之一对应的行和列后得到的n阶矩阵，Hn是从L（Pn+2）中删除路Pn+2的两个端点对应的行和列后得到的n阶矩阵.

引理2.5［10］设ϕ（P0）= 0，ϕ（B0）= 1，ϕ（H0）= 1.则有:引理2.6［6］如果µ/= 4，且y满足方程y2-（µ- 2）y + 1 = 0.则有以下结论:

设v是图G的一个顶点，令Lv（G）是从L（G）中删去顶点v对应的行和列后得到的L（G）的主子矩阵.

引理2.7［11］设图G = G1u : vG2是通过一条边连接图G1的顶点u和图G2的顶点v得到的图，则

ϕ（G）=ϕ（G1）ϕ（G2）-ϕ（G1）ϕ（Lv（G2））-ϕ（G2）ϕ（Lu（G1））.

引理2.8设图G是含有双圈G4～= K4- e作为点导出子图的连通双圈图.如果图G′与图G同Laplacian谱，则G′是一个含有双圈G4作为点导出子图的连通双圈图.

证因为图G和G′同Laplacian谱，由引理2.1知，图G′与图G的顶点数，边数及分支数数目相同，所以图G′一定为连通的双圈图.

设图G是n阶双圈图，根据上面结论以及双圈图的定义和它的三种分类，则n阶双圈图G′可能是三类双圈图An（p，q），Bn，m（p，q）和Cn（p，q）中的一种，下面证明n阶双圈图G′不可能是形如An（p，q）或Cn（p，q）的双圈图.因为由引理2.1知，图G和G′的生成树数目相同.而若图G′中的两个圈Cp和Cq（p，q≥3）有且只有一个公共顶点或无公共顶点，就是双圈图An（p，q）或Cn（p，q），此时它们的生成树数目都为pq≥9，这与图G的生成树数目为8矛盾.因此n阶双圈图G′只可能是双圈图Bn，m（p，q）（m≥2）.

下面证明n阶双圈图G′只能是m = 2，p = q = 3的双圈图Bn，m（p，q）= Bn，2（3，3）.因为若图G′是Bn，m（p，q）（m≥2），则它的两个圈Cp和Cq有m≥2个公共顶点，且有p≥（m + 1），q≥（m + 1），则图G′的生成树数目为

因此，上式等号成立当且仅当p = q = 3，m = 2.因此图G′～= Bn，2（3，3）.

因此，图G′～= Bn，2（3，3）是一个含有双圈G4作为点导出子图的连通双圈图.

令q3（G）= 6nG（C3）-Pni=1（di- 2）3.

引理2.9若图G′与图G同Laplacian谱，则q3（G）= q3（G′）.

由引理2.1和引理2.4易知，证明过程略.

引理2.10若图G与图G′同Laplacian谱，则

由引理2.1易知，证明过程略.

§3　主要结果

定理3.1双圈图Q（n；n1）（见图1）由其Laplacian谱确定.

证G = Q（n；n1）.设图G′与图G同Laplacian谱.设图G′由x′j个度为j的点，j = 1，2，···，△，其中，△是图G′中最大的度.根据引理2.2，△+ 1≤µ1（G）=µ1（G′）≤6，所以，△= d1（G′）≤5.由引理2.10和引理2.1的（1）可得:

（2）和（3）相加得:

因此，x′5= 0，x′4= 0，1.

（1）x′4= 1.图G′的度序列为（11，2n-3，31，41）.

（2）x′4= 0.图G′的度序列为（12，2n-6，34）.

由引理2.8知图G和G′中均含图G4（见图1），所含三角形个数均为2.又由引理2.9，q3（G）= q3（G′），可得图G′的度序列只可能为（11，2n-3，31，41）.所以图G′的形式是Q（n；n′1），根据引理2.1，n1= n′1，因此，图Q（n；n′1）与图Q（n；n1）同构.

引理3.1如果两个形如Q（n；n1，n2）（见图1）的图同Laplacian谱，则它们必定同构.

证令图G = Q（n；n1，n2）.设G′= Q（n；n′1，n′2）与图G同Laplacian谱.根据引理2.1，

根据引理2.3，得到:

式中Φ表示所有在图G中的G4（见图1）上删去三条边而得到的子森林.

相似的，

将（7），（8）代入（6），得到:

相似的，对l′n-2，有因为，所以

所以，G和G′同构.

定理3.2双圈图Q（n；n1，n2）（见图1）由其Laplacian谱确定.

证令图G = Q（n；n1，n2）.设图G′与图G同Laplacian谱.设图个度为j的点，j = 1，2，···，△，其中，△是图G′中最大的度.根据引理2.2，，所以，△= d1（G′）≤5.由引理2.10和引理2.1的（1）可以得到:

（12）和（13）相加得:

因此，x′5= 0，1.

（1）x′5= 1.图G′的度序列为（12，2n-4，31，51）.

（2）x′5= 0.图G′的度序列为（13，2n-6，31，42），（14，2n-9，34，41）或（15，2n-12，37）.

由引理2.8知图G和G′中均含图G4，所含三角形个数均为2.又由引理2.9，q3（G）= q3（G′），可得图G′的度序列只可能为（12，2n-4，31，51）.所以图G′的形式是Q（n；n′1，n′2），根据引理3.1，图Q（n；n′1，n′2）与图Q（n；n1，n2）同构.

引理3.2如果两个形如Q（n；n1，n2，n3）（见图1）的图同Laplacian谱，则它们必定同构.

证令图G = Q（n；n1，n2，n3）.设G′= Q（n；n′1，n′2，n′3）与图G同Laplacian谱.根据引理2.1，根据引理2.3，得到:

式中Φ表示所有在图G中的G4上删去三条边而得到的子森林.

相似的，

将（17）-（19）代入（16）可得:

类似的，

令G2= G（n - n3；n1，n2），G3= G（n - n2- n3；n1），G4= G（n - n1- n2- n3）.根据引理2.9，

当x /= 4时，根据引理2.6，由Maple计算可得:（26），（27）代入（23），可以得到:

其中，m = n1+ n2+ n3，

因为图G和图G′有相同的Laplacian特征多项式，即ϕ（G）=ϕ（G′），所以

不妨设n1≤n2≤n3≤n4，则）和）关于y的最低次幂分别为2n1+ 2和2n′1+ 2.因此n1= n′1.结合（15），（22）可得:因此，n2=，所以G和G′同构.

定理3.3 双圈图Q（n；n1，n2，n3）（见图1）由其Laplacian谱确定.

证令图G = Q（n；n1，n2，n3）.设图G′与图G同Laplacian谱.设图G′由个度为j的点，j = 1，2，···，△，其中，△是图G′中最大的度.根据引理2.2，

所以，△= d1（G′）≤6.由引理2.10和引理2.1的（1）可以得到:

（32）和（33）相加得:

因此，x′6= 0，1.

（1）x′6= 1.图G′的度序列为

（2）x′6= 0.图G′的度序列为），）），）或

由引理2.8知图G和G′中均含图G4，所含三角形个数均为2.又由引理2.9，q3（G）= q3（G′），可得图G′的度序列只可能为（13，2n-5，31，61）.所以图G′的形式是Q（n；n′1，n′2，n′3），根据引理3.2，图Q（n；n′1，n′2，n′3）与图Q（n；n1，n2，n3）同构.

引理3.3如果两个形如B（n；n1，n2）（见图1）的图同Laplacian谱，则它们必定同构.

证令图G = B（n；n1，n2）.设G′= B（n；n′1，n′2）与图G同Laplacian谱.根据引理2.1，

根据引理2.3，得到:

式中Φ表示所有在图G中的G4上删去三条边而得到的子森林.

相似的，

将（42），（43）代入（41）得到:

相似的，对ln-2′有

因为n1+ n2= n′1+ n′2，（-1）n-2ln-2=（-1）n-2l′n-2，所以

不妨设n1≤n2，n′1≤n′2，由（35），（39）可以得到:

所以，G和G′同构.

定理3.4双圈图B（n；n1，n2）（见图1）由其Laplacian谱确定.

证令图G = B（n；n1，n2）.设图G′与图G同Laplacian谱.设图G′由x′j个度为j的点，j = 1，2，···，△，其中，△是图G′中最大的度.根据引理2.2，△+ 1≤µ1（G）=µ1（G′）≤6 +，所以，△=≤5.由引理2.10和引理2.1的（1）可以得到:

（42）和（43）相加得:因此，x′5= 0，1.

（1）x′5= 1.图G′的度序列为（11，2n-2，51）.

（2）x′5= 0.图G′的度序列为（12，2n-4，42），（13，2n-7，33，41）或（14，2n-10，36）.

由引理2.8知图G和G′中均含图G4，所含三角形个数均为2.又由引理2.9，q3（G）= q3（G′），可得图G′的度序列只可能为（12，2n-4，42）.所以图G′的形式是B（n；n′1，n′2），根据引理3.3，图B（n；n′1，n′2）与图B（n；n1，n2）同构.

致谢衷心感谢审稿人的意见和建议.

［1］G¨unthard H H，Primas H. Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen［J］. Helv Chim Acta，1956，39: 1645-1653.

［2］Kac M. Can one hearing the shape of a drum？［J］. Amer Math Monthly，1966，73: 1-23.

［3］van Dam E R，Haemers W H. Which graphs are determined by their spectrum？［J］. Linear Algebra Appl，2003，373: 241-272.

［4］van Dam E R，Haemers W H. Developments on spectral characterizations of graphs［J］. Discrete Math，2009，309: 576-586.

［5］Liu Xiaogang，Wang Suijie，Zhang Yuanping. On the spectral characterization of some unicyclic graphs［J］. Discrete Math，2011，311: 2317-2336.

［6］Liu Xiaogang，Zhou Sanming. Spectral characterizations of propeller graphs［J］. Electronic J Linear Algebra，2014，27: 19-38.

［7］Kelmens A K，Chelnokov V M. A certain polynomial of a graph and graphs with an extremal number of trees［J］. J Combin Theory，Ser B，1974，16: 197-214.

［8］Li Jiongsheng，Zhang Xiaodong. On the Laplacian eigenvalues of a graph［J］. Linear Algebra Appl，1998，285: 305-307.

［9］Biggs N L. Algebraic graph theory［M］. 2nd ed. Cambridge: Cambridge University Press，1993，47-48.

［10］Guo Jiming. A conjecture on the algebraic connectivity of connected graphs with fixed grith［J］. Discrete Math，2008，308: 5702-5711.

［11］Guo Jiming. On the second largest Laplacian eigenvalue of trees［J］. Linear Algebra Appl，2005，404: 251-261.

MR Subject Classification: 05C50

Two kinds of bicyclic graphs are determined by their Laplacian spectra

WANG Zhan-qing，WANG Li-gong，MEI Ruo-xing，ZHAI Ruo-nan，DONG Zhan-peng
（Department of Applied Mathematics，School of Science，Northwestern Polytechnical University，Xi'an 710072；China）

Let G =（V（G），E（G））be a simple connected graph with vertex V（G）and edge set E（G）. Two graphs are said to be Laplacian cospectral if they have the same Laplacian spectrum. In this paper，two kinds of bicyclic graphs Q（n；n1，n2，···，nt）and B（n；n1，n2）are defined. It is proved that graphs Q（n；n1），Q（n；n1，n2），Q（n；n1，n2，n3），and B（n；n1，n2）are determined by their Laplacian spectra.

Laplacian matrix；Laplacian characteristic polynomial；Laplacian spectra

O157.5

A

1000-4424（2016）01-0073-10

2015-01-21

2016-01-26

，Email：lgwangmath@163.com

国家自然科学基金（11171273）；国家级大学生创新创业训练计划（201410699079）