单圈图依次小Q－特征值排序

周 敏， 何常香

（上海理工大学 理学院，上海 200093）

设G＝（V，E）是有n个顶点的简单连通图（不含环和多重边）.其中V＝｛v1，v2，…，vn｝是点集合，E＝｛e1，e2，…，em｝是边集合.图G的邻接矩阵定义为一个n×n矩阵A（G）＝（aij），其中当vi和vj相邻时，aij＝1；当vi和vj不相邻时，aij＝0.假如G是一个简单图，则A（G）是一个实对称的（0，1）－矩阵且它的主对角线上的元素全为0.

令d（vi）表示顶点vi的度，图G的无符号拉普拉斯矩阵定义为Q（G）＝D（G）＋A（G），其中D（G）是以G的所有顶点的度为对角元的对角阵.近年来，特别是文献［1］发表之后，关于无符号拉普拉斯矩阵的研究日益受到人们的关注.众所周知Q（G）是一个实对称的半正定矩阵，设其特征值为

qn（G）＝0当且仅当G有一个连通分支是二部图.对于图的无符号拉普拉斯最大特征值已经有了深入研究［2－5］，而对于图的无符号拉普拉斯最小特征值的研究相对较少，文献［6－8］给出了无符号拉普拉斯最小特征值的一些结论.

为方便起见，记图G的依次小Q－特征值为k（G）.显然，若G为二部图，则k（G）＝α（G），其中α（G）为G的代数连通度.关于最简单的连通图树的代数连通度已经有了很多结果［9－12］.本文主要研究单圈图（边数等于顶点数的连通图）的k（G）.记阶数为n的所有连通的单圈图的集合为U（n）.给出了当阶数n≥25时，U（n）中依次小Q－特征值为前3大的图.下面给出一些必要的定义.

定义1n阶图G叫做单圈图，如果G是连通的，并且G的边数也是n.

定义2 设G是一个单圈图，v是G圈上的点，如果d（v）≥3，则称v是G的一个分叉点.并记G的分叉点个数为Fork（G）.

定义3 设G是一个连通图，uv∈E（G），剖分边uv，即去掉边uv，同时增加一个新点w以及两条新边wu，wv.

对于整数n≥3，Cn表示有n个顶点的圈；Pn表示有n个顶点的路；Um（n）表示圈长为m≥3的n阶单圈图的全体所构成的集合；S（m，n）表示在星 图K1，m和K1，n的中心添加一条边所得的图；S＊（m，n）表示由根点长出m条长为2的悬挂路，n条悬挂边所得的有根树.

定义4 设Us（T1，T2，…，Ts）表示由圈v1v2…vsv1从它上面的点vi分别长出树Ti（1≤i≤s）（Ti是以vi为根点的有根树）所得的单圈图.以根点vi为端点的Ti最长路的长度称为有根树Ti的高.当Ti为S（m，n）（m≠1）且根点为星图K1，m的中心时，简记Ti为S（m，n）；当Ti为K1，m且根点为K1，m的中心时，简记Ti为m；若单圈图Us（T1，T2，…，Ts）中，Ti＋1，…，Ts的高均为0，将其简记为Us（T1，T2，…，Ti）.

定义5 设G＝G1u：vG2是由两个顶点不相交的连通图G1和G2通过连接G1中的点u和G2中的点v得到的图，则G叫做G1，G2关于点u，v的连通和.

定义6 对任意图G和v∈V（G），用Qv（G）表示由G的无符号拉普拉斯矩阵Q（G）去掉v对应的行和列后得到的主子阵.

对于只有非负根的方程P（x）＝0，记τ（P）为它的最小正根.若M是实对称阵，它的最小特征值也记为τ（M）.特别的，记Qv（P3）（其中v为P3的一个端点）的特征多项式x2－3x＋1为a（x），易得τ（a）≈0.382 00，记为τ0.

表1中列出的是一些在本文证明中用到的k（G）小于τ0的单圈图及其k（G）.

引理1［8］设G是一个n阶连通图，1≤k≤n＋1是一个自然数，H由G增加一个点u，并将u与G中1≤t＜k个点相连得到的图，则qk（H）≤qk－t（G）.

表1 k（G）＜τ0的单圈图及其k（G）Tab.1 Unicycle graph when k（G）＜τ0and its k（G）

引理2［13］设A＝B＋C，A，B，C均为n阶实对称阵，若C恰有t个正特征值，则有λk（B）≥λk＋t（A）（其中1≤k≤n－t）.

推论1 设图G是一个连通图，H由G增加一个悬挂点所得的图，则k（H）≤k（G）.

证明 设G的阶数为n，在引理1中取t＝1，k＝n，则qn（H）≤qn－1（G），即k（H）≤k（G）.

推论2 若H是单圈图，G是H的单圈子图，则k（H）≤k（G）.

证明 反复利用推论1即可得此结论.

引理3［14］设G是一个连通图，G′是由G将其一边连续剖分两次得到的图，则k（G′）≤k（G）.

结合推论1和引理3可得如下结果：

推论3 若图H去掉某悬挂边后可以得到G的某种偶次剖分，则k（H）≤k（G）.

引理4［15］设n阶图G是由图H从点ν长出t条新悬挂边得到的图，则ψ（G）＝ （x－1）t ψ（H）－tx（x－1）t－1ψ（Qv（H））

引理5［16］设A是一个n阶的Hermitian矩阵且具有特征值λ1≥λ2≥…≥λn.设B是A的一个m阶主子阵，具有特征值μ1≥μ2≥…≥μm，则λn－m＋i≤μi≤λi（i＝1，2，…，m）.

1 等于τ0的单圈图

记由n阶单圈图U3（S＊（s，t）），U3（1，S＊（s，t）），U3（1，1，S＊（s，t）），U4（S＊（s，t）），U4（1，S＊（s，t）），U5（S＊（s，t）），U5（n－5），U3（1，1，n－5）（s≥1）组成的图类为C1类图（见图1）.

图1 C1类Fig.1 C1class

定理1 a.当s≥2时，U3（S＊（s，t）），U3（1，S＊（s，t）），U4（S＊（s，t））的 依 次 小Q－ 特 征 值 等于τ0.

b.当s≥1 时，U3（1，1，S＊（s，t）），U4（1，S＊（s，t）），U5（S＊（s，t））的 依 次 小Q－ 特 征 值 等于τ0.

c.当s≥1时，U5（n－5）的依次小Q－特征值等于τ0.

d.当s≥5时，U3（1，1，n－5）的依次小Q－特征值等于τ0.

证明a.令v是U3（S＊（s，t））唯一的分叉点，则Qv（U3（S＊（s，t）））是s个Qv（P3），t个Qv（P2）和一个Qv（C3）的直和.经计算

故τ0＝τ（Qv（U3（S＊（s，t））））且重数是s，所以由引理5知当s≥2时，k（U3（S＊（s，t）））＝τ0.

同理可证U3（1，S＊（s，t）），U4（S＊（s，t））的依次小Q－特征值等于τ0.

b.令v是U3（1，1，S＊（s，t））中长出s条长为2的悬挂路的分叉点，则Qv（U3（1，1，S＊（s，t）））是s个Qv（P3），t个Qv（P2）和一个Qv（U3（1，1））的直和，v是P3的端点，同时也是U3（1，1）中的一个圈上的非分叉点.经计算

故τ0＝τ（Qv（U3（1，1，S＊（s，t））））且重数是s＋1，所以由引理5知当s≥1时，k（U3（1，1，S＊（s，t）））＝τ0.

同理可证U4（1，S＊（s，t）），U5（S＊（s，t））的依次小Q－特征值等于τ0.

c.当s≥1时

f（τ0）＜0，f（x）是 4 次的，则τ0＞τ（f）.f（－∞）＝＋∞，f（1）＜0，f（3）＞0，f（4）＜0，f（＋∞）＝＋∞.则f（x）在（－∞，1），（1，3），（3，4），（4，＋∞）上有根.所以f（x）的第二小根是大于τ0的，从而τ0是U5（n－5）的依次小Q－特征值.

d.当s≥5时

f（－∞）＝＋∞，f（τ0）＜0，f（1）＞0，f（5）＜0，f（＋∞）＝＋∞.所以f（x）的第二小值是大于τ0的，从而τ0是U3（1，1，n－5）的依次小Q－特征值.

2 k（G）小于τ0的单圈图

记由n阶单圈图G1＝U3（n－3），G2＝U4（n－4），G3＝U3（1，n－4），G4＝U4（1，n－5），G5＝U3（S＊（1，n－5）），G6＝U4（S＊（1，n－6）），G7＝U3（1，S＊（1，n－6））组成的图类为C2类图（见图2）.

图2 C2类Fig.2 C2class

任何一个单圈图G，若它含有表1中列举的任一图的偶次剖分作为单圈子图，由推论3知k（G）＜τ0.所以证明阶数n≥25的非C1，C2类单圈图必以表1列举的某一图或其偶次剖分作为单圈子图.在引理6～8中，将按照单圈图的分叉树的最大高度来讨论.

引理6 设n阶单圈图G的分叉树均是以中心为根的星图（即分叉树的最大高度为1），若n≥25且G不为C2类图，则k（G）＜τ0.

证明 证明G以表1中的某个图（设为G0）或其偶次剖分图为单圈子图，则k（G）≤k（G0）＜τ0.设单圈图的圈长为l.

情形1l≥11

若l为奇数，则必以C11或其偶次剖分为单圈子图.若l为偶数，则必以C12或其偶次剖分为单圈子图.

情形2l＝10

由于n≥25，G必以U10（1）为单圈子图.

情形3l＝9

G必以U9（1）为单圈子图.

情形4l≤8

子情形al＝8.由n≥25知，G必以U8（2）为单圈子图.

子情形bl＝7.由n≥25知，G必以U7（3），U7（2，0，2）之一为单圈子图.

子情形cl＝6

若G中有阶数大于6的分叉树，则G必以U6（6）为单圈子图.若G中分叉树的阶数均小于等于6，由n≥25知G至少以U4（2，0，4），U4（4，4）之一的偶次剖分为单圈子图.由于G的分叉树均是以中心为根的星图，且G不是G1，G2，U5（n－5），故当圈长l≤5时，只需考虑分叉点数Fork（G）≥2的情形.

子情形dl＝5

若G中有阶数大于10的分叉树，则G至少以U5（1，11），U5（3，4），U5（1，0，5）之一为单圈子图.若G中分叉树的阶数均小于等于10，由n≥25知G至少以U5（3，4），U5（2，0，3），U5（1，0，5）之一为单圈子图.

子情形el＝4

子情形（a）Fork（G）＝2

首先考虑G中有一个2阶分叉树的情况.由于G不是G4，故G的这两个分叉点不相邻，由n≥25可知G必以U4（1，0，12）为单圈子图.当G中分叉树的阶数都大于2时，由n≥25知G至少以U4（2，8），U4（2，0，4），U4（4，4）之一为单圈子图.

子情形（b）Fork（G）＝3

若G中恰有一个分叉树阶数大于2，由n≥25可知G至少以U4（1，1，7），U4（1，17，1）之一为单圈子图.若G中有两个分叉树阶数都大于2，G至少以U4（2，8），U4（2，0，4），U4（4，4）之一为单圈子图.

子情形（c）Fork（G）＝4

若G中恰有一个阶数大于2的分叉树，G必以U4（1，1，1，6）为单圈子图.若G中有两个阶数大于2的分叉树，由n≥25可知G至少以U4（2，8），U4（2，0，4），U4（4，4）之一为单圈子图.

子情形fl＝3

子情形（a）Fork（G）＝2

由于G不是G3，故G中的两个分叉树的阶数都大于2，由n≥25可知G至少以U3（2，20），U3（3，7），U3（4，5）之一为单圈子图.

子情形（b）Fork（G）＝3

由于G不是U3（1，1，n－5），故G中有两个阶数大于2的分叉树，由n≥25可知G至少以U3（3，7），U3（4，5），U3（1，2，12），U3（2，2，8）之 一 为单圈子图.

引理7 设G为n≥19阶单圈图，若G的所有分叉树的最大高度为2，且G不为C1，C2类图，则k（G）＜τ0.

证明 思路与定理1一样.

情形1l≥11

若l为奇数，则必以C11或其偶次剖分为单圈子图.若l为偶数，则必以C12或其偶次剖分为单圈子图.

情形2l＝10

由于n≥25，G必以U10（1）为单圈子图.

情形3l＝9

G必以U9（1）为单圈子图.

情形4l≤8

当G中至少有两个分叉树的高为2时，G至少以U3（P3，P3，1），U3（P3，S＊（1，1）），U4（P3，P3），U4（P3，0，P3）之一的偶次剖分为单圈子图.

当G中只有一个分叉树的高为2时，若此分叉树有顶点（除根点外）度数大于2，由n＞17，G必以U3（2，P3），U4（S（0，2））之一的偶次剖分为单圈子图.所以，假设G中只有一个分叉树的高度为2，且分叉树上的点（除根点和悬挂点外）均为2度点.设l为G中圈的长度.

子情形al＝3

若Fork（G）＝2，即G某个U3（r，S＊（s，t）），由于G不是G7，故r＞1，从而G必以U3（2，P3）为单圈子图.

若Fork（G）＝3，即G为某个U3（q，r，S＊（s，t）），由于G不是U3（1，1，S＊（s，t）），所以q，r中必有一个大于1，进而有G以U3（2，P3）为单圈子图.

子情形bl＝4若Fork（G）＝2，若G的两个分叉点相邻，由于G不是U4（1，S＊（s，t）），G必以U4（2，P3）为单圈子图；若G的两个分叉点不相邻，G必以U4（1，0，P3）为单圈子图.若Fork（G）＞2，则G也必以U4（1，0，P3）为单圈子图.

子情形cl＝5

Fork（G）≥2，则G以U3（2，P3）的偶次剖分或U5（S＊（1，1），1）为单圈子图.

子情形dl＝6

G至少含U6（P3）或U4（1，0，P3）的偶次剖分为单圈子图.

子情形el＝7

G至少含U5（1，P3）或U5（1，0，P3）的偶次剖分之一为单圈子图.

子情形fl＝8

G必含U6（P3）的偶次剖分为单圈子图.

引理8G为n阶单圈图，若G分叉树的最大高度大于2，则k（G）＜τ0.

证明 此时G至少含U4（P4），U7（P4）（的偶次剖分）之一为单圈子图.

当l＝3时，G必含U3（P3，P4）为单圈子图.

当l＝5时，G必含U5（P3，P4）为单圈子图.

由引理6～8可得：

定理2 当n≥25时，所有不是C1，C2类的n阶单圈图的依次小Q－特征值均小于τ0.

3 k（G）大于τ0的单圈图

定理3 当n≥25时

k（G1），k（G2），k（G3），k（G4），k（G5），k（G6），k（G7）都是大于τ0的.

首先由引理4可知Gi（i＝1，…7）的无符号拉普拉斯特征多项式为

证明 首先证明k（G1）＞τ0，f1（x）＝x3－（n＋3）x2＋3nx－4，对f1（x）求导，f1′（x）＝3x2－2（n＋3）x＋3n，当x＜1时，f′1（x）＞0，则f1（x）在（－∞，1）上是单调递增的，又f1（－∞）＝－∞，f1（1）＝2n－6＞0，所以f1（x）＝0在（－∞，1）恰有一根，故k（G1）＝1＞τ0.

再证k（G2）＞τ0.

f2（x）＝（x2－3x＋1）（x－n）＋（n－3）x－n.当x＜τ0时，x2－3x＋1＞0，x－n＜0，（n－3）x－n＜0.所以f2（x）＜0，则τ（f2）＞τ0.综上k（G2）＞τ0.k（G4）＞τ0，k（G6）＞τ0同理可证.

下证k（G3）＞τ0.

经计算f3（x）＝f2（x）（x2－2x－1）－6x2＋（3n＋6）x－4－2n，f3（－∞）＝－∞，f3（τ0）＞0，f3（1）＜0，f3（2）＞0，f3（4）＜0，f3（25）＞0.显然k（G3）＞τ0.

k（G5）＞τ0，k（G7）＞τ0同理可证.

4 主要结果

设C1，C2类图分别如图1和图2所示，由定理1、定理2和定理3可得本文的主要结论.

定理4 如果G是一个n≥25阶单圈图，则

a.k（G）＝，当且仅当G是C1类图.

b.k当且仅当G是C2类图.

c.k当且仅当G既不是C1类，也不是C2类的单圈图.

［1］CvetkovicˇD M.Signless Laplacian and line graph［M］.Berlin：Mathematiques Naturelles，2005.

［2］Wang J F，Huang Q X，Francesco B.On graph whose signless Laplacian index does not exceed 4.5［J］.Linear Algebra and Its Applications，2009，431（1）：162－178.

［3］Kinkar C D.On conjectues involving second largest signless Laplacian eigenvalue of graphs［J］.Linear Algebra and Its Applications，2010，432（11）：3018－3029.

［4］Wang J F，Francesco B，Huang Qiongxiang.On the two largesr Q－eigenvalues of graphs［J］.Discrete Mathematics，2010，310（21）：2858－2866.

［5］Chen Y Q，Wang L G.Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph［J］.Linear Algebra and Its Applications，2010，433（5）：908－913.

［6］Leonardo S L，Carla S，Nair M A.The smallest eigenvalue of the signless Laplacian ［J］.Linear Algebra and Its Applications，2011，436（10）：2570－2584.

［7］Cardoso D M，Cvetkovic D，Rowlinson P.A sharp lower bound for the least eigenvalue of the signless Laplacian of a non－bipartite graph［J］.Linear Algebra and Its Applications，2008，429（12）：2770－2780.

［8］He C X，Zhou M.The least Q－eigenvalue of graph［J］.Journal of East China Normal University，2012，163（3）：1－5.

［9］Liu Y.The ordering of limit point of algebraic connectivity of trees［J］.Journal of Natural Science of Heilongjiang University，2008，25（1）：103－106.

［10］Gu L，Yuan W G，Zhang X D.Algebraic connectivity of trees with the maximum degree［J］.Journal of East China Normal University，2011，163（3）：29－34.

［11］Liu Y，Shao J Y，Yuan X Y.The ordering of trees with perfect matching by the algebraic connectivity［J］.Advanced in Mathematics，2008，37（3）：270－282.

［12］Fan Y Z.A new proof of Fiedler’s inequality on the Algebraic connectivity of trees ［J］.Journal of Mathematical Study，2003，36（4）：289－383.

［13］Grone R，Merris R.The Laplacian spectrum of a graph［J］.SIAMJ Matrix Analytics and Apply，1990，11（2）：218－238.

［14］He C X，Hao P.The smallest signless Laplacian eigenvalue of graphs under perturbation［J］.ELA，2012，310（23）：473－482.

［15］CvetkovicD M，Doob M，Sachs H.Spectra of graphs［M］.New York：Academic Press，1980.

［16］CvetkovicD M，Doob M，Sachs H.Spectra of graphstheory and application ［M］.Heidelberg：Johann Ambrosius Barth Verlag，1995.