几类正惯性指数为2的图的刻画

彭杨　耿显亚　朱娜

摘 要：图G的正惯性指数p（G）定义为图G的邻接矩阵A（G）中正特征值的个数.正惯性指数为2的图的刻画仍是未解决的问题.本文刻画正惯性指数p（G）=2的树、单圈以及双圈图.

关键词：邻接矩阵; 图的正惯性指数; 图的秩

[中图分类号]O157.6   [文献标志码]A

Several Types of Graphs with Positive Inertia Index 2

PENG Yang，GENG Xianya，ZHU Na

（School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001，China）

Abstract：The positive inertia index of a graph G is p（G），which is defined as the number of positive eigenvalues of adjacency matrix A（G）.The characterization of a graph with a positive inertia index of 2 remains a unresolved problem.This paper characterizes trees，unicyclic and bicyclic graphs with positive inertia index p（G）=2.

Keywords： Adjacency matrix; Positive inertia index of graphs; Rank of graphs

Key words：adjacency matrix;positive inertia index of graphs;rank of graphs

圖的惯性指数研究源自于上世纪量子化学中E.Hu··ckel发现的重要现象——E.Hu··ckel理论.该理论表明，不饱和碳氢化合物的分子活跃性与其分子图对应的零度及正惯性指数有密切关系.[1-2]1957年图论学家提出要刻画所有的奇异图这一公开问题[3]——刻画所有零度大于零的图的问题——对图的惯性指数的刻画成为图谱理论的热点问题之一.很多学者得到了一些有意义的结果[4-7]，但正惯性指数为2的图的刻画仍是未解决的问题，故笔者刻画了正惯性指数为2的树、单圈以及双圈图.

1 主要引理

本文考虑的是简单、连通、无序的图.令G=（V，E），其中V=v1，v2，…，vn是非空的顶点集，E=e1，e2，……，em是边集.图G的邻接矩阵A（G）=（aij）是对称矩阵，定义为：如果vi和vj相邻，则aij=1，否则aij=0.假设V′是V的一个非空子集，以V′为顶点集，以两端点均在V′中的边的全体为边集所组成的子图，称为G的由V′导出的子图，记为G[V′].G[V′]称为G的导出子图，简记为GΔG[V′].四个邻接矩阵的谱参数：图G的正惯性指数p（G）就是图G的邻接矩阵A（G）的正特征值的数目.图G的负惯性指数n（G）就是图G的邻接矩阵A（G）的负特征值的数目.图G的零度η（G）就是图G的邻接矩阵A（G）的零特征值的重数.图G秩r（G）就是图G的邻接矩阵A（G）的秩.显然，对于以上四个参数，有以下两个自然得到的等式.

p（G）+n（G）+η（G）=|V|， p（G）+n（G）=r（G）.

在本文中用uv表示在顶点u和顶点v之间添加的边.顶点v的邻域记为NG（v）={u|uv∈E（G）}.并且图G的顶点v的度dG（v）是G中与v关联的边的数目，即dG（v）=|NG（v）|.若NG（u）=NG（v），称顶点u和顶点v是一对孪生点; 若图G中没有孪生点，称G是简约的.

引理1[1] 如果图G是树，μ（G）是G的匹配数，则r（G）=2μ（G）.

引理2[4] 如果图G是树，μ（G）是G的匹配数，则p（G）=n（G）=μ（G）.

引理3[4] 如果G是包含一个悬挂点的图，H是G删去悬挂点以及与悬挂点相邻的顶点所得到的导出子图，则p（G）=p（H）+1，n（G）=n（H）+1，η（G）=η（H）.

引理4[5] 图G包含两个顶点u，w，如果≠NG（u）NG（w），H=G-{wv|v∈NG（u）}，则r（H）=r（G），p（H）=p（G）.特殊地，若NG（u）=NG（w），则r（G）=r（G-w），p（G）=p（G-w）.

引理5[1] 记Pn与Cn分别为阶数为n的路与圈.

（1）对Pn，有

引理6[7] 若图H是图G的一个导出子图，则r（H）≤r（G），η（H）≤η（G），p（H）≤p（G），n（H）≤n（G）.

2 刻画三类正惯性指数恰为2的简单连通图

由引理4可知，若已知G是满足p（G）=2的图，则在G上添加任意多的孪生点，得到的新图的正惯性指数仍保持为2.故而只考虑p（G）=2的简约图.

2.1 对于树

定理1 对于树G，p（G）=2当且仅当G=G1或G=G2.

证明 由引理2，可得p（G）=n（G）=μ（G）.所以，当p（G）=2时，μ（G）=2.可知该树的秩为4.因只考虑G是简约图的情形，由参考文献[5]可知， 树中秩为4的简约图只有G1和G2，所以G=G1或G=G2.

2.2 对于单圈图

定理2 对于单圈图G，p（G）=2当且仅当G=G5，G=G6，或G=G7.

证明 若图G包含五圈或更长的圈，则该圈是此单圈图中的导出子图，由引理5可知，此导出子图的正惯性指数严格大于2.又根据引理6，p（G）≥3.因此，图G只能包含三圈或四圈.

2.2.1 对包含三圈的单圈图

对于图G3和G4，应用引理3计算可知，p（G3）=p（G4）=3，要求p（G）=2，故GΔG3且GΔG4.因要求圖G是简约的，故而包含三圈的单圈图只可能是图G5，G6，G7，G8和G9中的某些.由引理3得，p（G5）=p（G6）=p（G7）=2，而p（G8）=p（G9）=3.因此，满足要求的图只有G5，G6和G7.

2.2.2 对包含四圈的单圈图

对G10，因为NG10（v1）=NG10（v3），NG10=（v2）=NG10（v4），所以在G10上只添加不超过一个悬挂点，或者悬挂点只挂在相对的顶点上（v1和v3，或v2和v4）时，所得的图都不是简约图.故必存i∈{1，2，3，4}使得d（vi）≥3.因此图GΔG11.但是p（G11）>2， 从而GΔ/G11.得出矛盾，即p（G）=2的单圈简约图不能包含四圈.

综上所述，满p（G）=2足的单圈图只有G5，G6，G7.

2.3 对于双圈图

定理3 对于双圈图，若p（G）=2，当且仅当G=G16，或G=G17，或G=G18，或G=G21，或G=G24，或G=G27.

证明 对于双圈图G，如果G包含五圈或更长的圈作为导出子图，由引理5可知，此导出子图的正惯性指数严格大于2.又根据引理6，p（G）≥3.因此，G只能是两个三圈、一个三圈和一个四圈，或两个四圈组成的双圈图.

2.3.1 G包含两个三圈

（1）两个三圈之间有一条公共边，如图G12所示.因为NG12（v1）=NG12（v3），所以当i=1，3时至少

有一个dG（vi）≥3.又因为p（G13）=p（G14）=p（G15）=3，所以GΔ/G13，GΔ/G14，GΔ/G15.因此得出

G16和G17可能满足， 由引理3可得p（G16）=p（G17）=2，故G16和G17满足要求.

（2） 如果两个三圈之间只有一个公共顶点，如图G18所示.因为p（G19）=p（G20）=3， 所以GΔ/G19，GΔ/G20.因此在这种情况下只有G18可能满足.经计算p（G18）=2，只有图G18满足.

（3） 如果两个三圈之间没有公共顶点，那么两个三圈之间至少有一条边.设两个三圈之间的路的长度为k，当k≥2时，图G会包含G3作为导出子图.由定理2可知GΔ/G3.因此，k只能为1.当k=1（如图G21）时，经计算p（G21）=2满足.如果对图G21加悬挂点，如图G22和G23，由引理3可得p（G22）=p（G23）=3，故GΔ/G22，GΔ/G23.因此，在这种情况下只有G21满足.

2.3.2 G是包含一个三圈和一个四圈的双圈图

（1） 如果三圈和四圈之间有一条公共边，如图G24.由引理3可得，p（G25）=p（G26）=p（G28）=3，故GΔ/G25，GΔ/G26，GΔ/G28.因此，只有图G24和G27可能满足.经计算p（G24）=p（G27）=2.故在这种情况下只有G24和G27满足.

（2）如果三圈和四圈之间只有一个公共点，如图G29.因为NG29（v4）=NG29（v6），故dG（v4）≥3和dG（v6）≥3至少有一个成立.因为由引理3得p（G30）=3，所以GΔ/G30.因此，在这种情况下没有满足条件的简约图.

（3）如果三圈和四圈之间没有公共点，则三圈和四圈之间至少有一条边.那么GΔ/G3. 由定理2可得GΔ/G3，矛盾.因此没有满足条件的简约图.

2.3.3 G是包含两个四圈的双圈图

（1）两个四圈之间有两条公共边（如图G31所示）.因为图G31中NG31（v2）=NG31（v3）=NG31（v4），要使图G中没有孪生点，则dG（v2）≥3，dG（v3）≥3，dG（v4）≥3中至少要有两个成立.因为由引理3得p（G32）=3，所以GΔ/G32.故在这种情况下没有满足条件的简约图.

（2）两个四圈之间只有一条公共边（如图G33）.由引理3和引理4可得p（G33）=3，故GΔ/G33.因此，在这种情况下没有满足要求的简约图.

（3）两个四圈之间只有一个公共顶点（如图G34）.因为NG34（v2）=NG34（v7），NG34（v4）=NG34（v6），所以要使图G中没有孪生点，则dG（v2）≥3和dG（vi）≥3（i=4，6），或者dG（v7）≥3和dG（vi）≥3（i=4，6）.如果满足这个条件，经计算p（G）≥3不满足，因此，在这种情况下没有满足要求的简约图.

（4） 两个四圈之间没有公共顶点， 那么两个四圈之间至少有一条边.因此，图G包含P6作为导出子图.由引理3得p（P6）=3，故p（G）≥3.因此，在这种情况下没有满足条件的简约图.

综上所述，对于满足p（G）=2的双圈图，只有图G16，G17，G18，G21，G24，G27.

参考文献

[1]D.Cvetkovic′，M.Doob，H.Sachs.Spectra of Graphs[M].New York：Academic Press，1980.123-136.

[2]方国斌，李萍.基于马尔可夫链的国内废水排放量预测[J].牡丹江师范学院学报：自然科学版，2020 （1）：6-10.

[3]E.Hu··ckel.Quantentheoretische Beitra··ge zum Benzolproblem[J].Z.Phys.，1931，70：204-286.

[4]X.Li，G.Yu.The skew-rank of graphs[J].Scientia Sinica Math，2015，45：93-104.

[5]J.H.Smith.Some properties of the spectrum of a graph[J].Combinat.Structures and their appl.，Gordon and Breach，1970：403-406.

[6]刘英伟，张洋.任意螺旋线拓扑数值解法[J].牡丹江师范学院学报：自然科学版，2019（3）：13-17.

[7]L.Wang，Y.Fan，Y.Wang.The Triangle-Free Graphs with Rank 6[J].Journal of Mathemtical Research with Applications.，2014，34（5）：517-528.

编辑：琳莉

收稿日期：2020-09-27

基金项目：安徽省自然科学基金项目（2008085MA01）

作者简介：彭杨（1996-），女，安徽淮南人.硕士研究生，主要从事图论及其应用的研究;耿显亚（1981-），男，安徽淮南人.教授，博士，主要从事图论及其应用的研究;朱娜（1995-），女，安徽淮南人.硕士研究生，主要从事图论及其应用的研究.