树的零度与路覆盖数的关系.pdf

第39 卷第4期2023年8 月Journal of Harbin University of Commerce(Natural Sciences Edition)哈尔滨商业大学学报（自然科学版)Vol.39 No.4Aug.2023树的零度与路覆盖数的关系陈洁，王龙（安徽理工大学数学与大数据学院，安徽淮南2 32 0 0 0）摘要：图的零度是指图G的邻接矩阵A（G）零空间的维度，亦等于其零特征值的重数,用n(G)表示.图的路覆盖是指图G中一组顶点不相交的诱导路的集合，使G的每个顶点都是其中一条路的顶点，G的路覆盖数是指G的最小路覆盖，用p（G）表示.2 0 2 1年Wang给出了图G的零度与路覆盖数的关系：n(G)p(G),本文刻画了所有满足n(G)=p(G)的树.关键词：图；树；秩；悬挂点；路；零度；路覆盖数中图分类号：0 157.6文献标识码：A文章编号：16 7 2-0 9 46(2 0 2 3)0 4-0 453-0 3Nullity of a tree in terms of path cover numberCHEN Jie,WANG Long(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan 232000,China)Abstract:The nullity of a graph G,referred to the dimension of the zero space of theadjacency matrix A(G),which was also equal to the multiplicity of zero eigenvalues.andwas expressed by n(G).The path cover of a graph referred to the set of induced paths withdisjoint vertices in a graph G,such that each vertex of G was the vertex of one of the paths.And the path cover number of G referred to the minimum path cover of G,denoted by p(G).In 2021,Wang gave the relationship between the nullity of a graph G and the number of pathcovers:n(G)p(G).In this paper,the trees that satisfied the(G)=p(G)werecharacterized.Key words:graph;tree;rank;pendent vertex;path;nullity;path cover number近年来展开了很多关于连通图的零度与其他结构参数例如图的匹配数m(G)、圈空间维数0(G)等之间关系的研究在文献1-15中对零度相关知识进行了广泛研究，19 7 5年Collatz和收稿日期：2 0 2 2-10-11.基金项目：中国博士后科学基金（2 0 19 M660148）作者简介：陈洁（19 9 9），女，硕士研究生，研究方向：图论研究，E-mail：2 8 2 517 37 18 q q.c o m；王龙（19 8 8-），男，副教授，博士，研究方向：图论研究，E-mail：w a n g l o n g x u z h o u 12 6.c o m.Sinogowitz提出了描述所有奇异图的问题；在文献2-7 中,分别给出了单圈图、双圈图、三圈图及树的线图的零度;Zhou等人在8 中用图的阶和最大度来描述图的零度的上界;Song等人在文献9 454中描述了所有零度为|V(G)|-2m（G）+2 c（G)的图；Wang给出了图的匹配数、边色数和独立数与秩的关系，和任意一个图零度的上下界10-;2 0 16年Ma等人给出了任意一个图的零度与圈空间维数和悬挂点数之间的关系12；李鑫研究了图的零度与独立数、悬挂点数关系13;CvetkovicD刻画了二部图谱中零的代数多重性14;2 0 19 年Wang对块都是圈或团的图的零度与路径覆盖数之间的关系进行了刻画15 本文主要研究的是树的零度与路径覆盖数之间的关系,刻画了所有满足m（G）=p(G)的树.与Wang在文献15中描述的区别在于其刻画的是块都是圈和团组成的图,本文研究的是连通的无圈图的零度与路覆盖数之间的关系.1预备知识本文研究的是无向的树,树是指任意两个顶点之间有且只有一条路径的无圈图.记简单无向图G的顶点集为V(G),边集为E(G).图 G的邻接矩阵A(G）=（a）n n,其中若v;与u,相邻,则aj=l;否则a；=0.图G的秩定义为其邻接矩阵A(G)的秩，零度定义为其邻接矩阵A（G）零特征值的重数,分别用r(G),n(G)表示,两者之间存在等式r(G）+n（G）=V(G)l.图的路覆盖是指图G中一组顶点不相交的诱导路（单个顶点的路径长为0）的集合，使G的每个顶点都是其中一条路的顶点,G的路覆盖数是指G的最小路覆盖,用p(G）表示.图G中点的度表示与相邻的边的数目，记作dc（).若dc（）=1,则点表示图G的一个悬挂点.G中一条路P只有一个顶点与G中其他部分相连接，则称路P是图G的一个悬挂路.用GU 表示从图G中删去U的顶点及其相关联的边,其中UCV(G),若H是图G的诱导子图,直接用符号GH 表示.对于诱导子图H和H外一点x,顶点集V(H）U 的G的诱导子图可记为H+x.用P，表示有n个顶点的路.下面给出本文结论证明中需要用到的一些重要引理.引理1.114：对一条路P,，若n是奇数，则n(P,）=1;若n是偶数,则n(P,）=0.哈尔滨商业大学学报（自然科学版）H是由G删去这个悬挂点及其相邻的点得到的诱导子图,则n(G)=n(H).引理1.315：设G是包含一个悬挂点的图，图H是由G删去这个悬挂点及其相邻的点得到的诱导子图,则p(H)p(G).引理1.415：若G是连通图，则n(G）p(G).2主要结果及证明Wangl15给出并证明了连通图G的零度与路覆盖数之间存在n(G）p（G）的关系,因此当 G是树时,其零度和路径覆盖数之间也存在关系式n(G）p(G).下面我们来讨论在树中(G）=p（G）成立的充分必要条件.首先给出了一些相关图、操作以及集合的定义.图P：中心点a的度为p+r,有p+r条悬挂路P2s+1,其中r条悬挂路P2s+1上与中心点相邻的顶点与一条P2.的悬挂点相连接(p2,r0).操作A：对G中奇路上任意点与图P的中心点相连,其中在悬挂点与图P相连时p1.定义集合T:1)奇路P2n+1T;2)若图GT,对 G进行操作A得到 G,则 GE T.在证明树中n（G）=p(G）成立的充分必要条件之前我们先给出一个引理及其证明.引理2.1：若图GE T,在G的非悬挂点上与P2n的一个悬挂点相连后得到G,GT则p(G)=p(G)+1.证明：G是路P2n+1时,p（G）=1.在P2n+1非悬挂点上与P2n的一个悬挂点相连得到G,GT,p(G)=2.有p(G)=p(G)+1.若P是图P中心点的相邻点与P2n的一个悬挂点连接时得到的图,此时,P=T,则是在图P（除去中心点的相邻点和悬挂点）上与P2n的一个悬挂点相连得到,则p(P）=p-1+r+1=p+r.若G是由路P2n+1经过n次操作A得到,G是在图G的非悬挂点上与P2n的一个悬挂点相连得到,G T.用归纳法来证明.n=1时,p(G)=1+p(P)=1+p-1+r=p+r,p(G)=1+p(P)=1+p+r.有p(G)=p(G)+1.第39 卷引理1.2 14：设G是包含一个悬挂点的图，图第4期假设n=k时,p(G)=p(G)+1成立.下面来证明n=k+1时的情况.设B是由路P2n+1经过k次操作A得到，在B上经过1次操作A得到G,此时p(G)=p(B）+p(P）=p(B）+p-1+r.若G是在第(k+1)次操作A中的图P(除去中心点的相邻点和悬挂点）上与P2n连接得到，则p(G)=p(B)+p(P)=p(B)+p+r.若G是在B中某个图P(除去中心点的相邻点和悬挂点)上与P2,连接得到,则p(G）=p(B+P2 n）+p(P).又p(B+P2n)=p(B)+1,则p(G)=p(B+P2n)+p(P)=p(B)+1+p-1+r=p(B)+p+r.有p(G)=p(G)+1.证毕.定理2.2:若G是树,m(H）=p(G)当且仅当G T.证明：首先证明充分性，若C是路P2m+1，n(G)=1,p(G)=1.则 n(G)=p(G).若G是由路P2n+1经过n次操作A得到,用归纳法来证明.n=1时,G是由路P2n+1经过一次操作A后得到时，设是图P中p条悬挂路P2s+1上的一个悬挂点，y是与相邻唯一顶点，令H=G-y.根据引理1.2,n(H）=m(G),经过（s+1)次操作后，得到一条奇路P2n+1,P-1条路P2s+1和r条奇路，则n(G)=n(P2n+1)+（p-1)n(P2 s+1）+r=p+r.又p(G)=1+p-1+r=p+r,则m(G)=p(G).假设n=k时,n(G)=p(G)成立.下面来证明n=k+1时的情况.设B是由路P2n+1经过k次操作A得到,在B上经过1次操作A得到G.B中奇路上任意点与图P相连后，设是图P中p条悬挂路P2s+1上的任意一个悬挂点，y是与相邻唯一顶点，令H=G-y.根据引理1.2,n(H）=n(G),经过(s+1)次操作后,得到图 B和(p-1)条路P2s+1和r条奇路，则n(G)=n(B)+(p-1)n(P2+1)+r=n(B)+p-1+r又p(G)=p(B)+p-1+r,且n(B)=p(B),则n(G)=p(G).必要性:根据引理1.4,对图 G,都有(G)p(G).假设GT,证明其都满足n（G）p(G)即陈洁，等：树的零度与路覆盖数的关系可.设是G的一个垂点，是与相邻的唯一顶点,令H=G-,要证明n(G)p(G).此时 H可分为两种情况：情况1:HT,由引理1.2,得到（H）=n(G),由引理1.3 得到p(H)p(G).对 G的顶点进行归纳,K T,利用数学归纳法,由于 H=G-K,是G的子图,假设n(H)p(H),则n(G)=n(H)p(H)p(G)情况2:HeT,则G是在H中除了悬挂点的任意顶点上连接一个路P得到的图，设是路P，与H相连后的路P上的悬挂点,y是与相邻唯一顶点,令 H=C-x-y,根据引理 1.2,n(H)=n(G).又根据充分性中证明有(H）=p(H),则m（G)=p(H).根据引理2.1,此时p（G）=p（H）+1,则n(G)p(G).证毕.参考文献：1COLLATZ L,SINOGOWITZ U.Spektren endlicherGrafenJ.Abh.Math.Sem.Univ.Hamburg,1957,21:63 77.2CHENG B,LIU B.On the nullity of graphs J.Electron.J.Linear Algebra,2007,16:60-67.3TAN X Z,LIU B L.On the nullity of unicyclic graphsJ.Linear Algebra Appl,2005,408:212-220.4HU S.On the nullity of bicyclic graphs J.LinearAlgebra Appl,2008,429(7):1387-1391.5 LI J,CHANG A,SHIU W C.On the nullity of bicyclicgraphs J.Match Commun.Math.Comput.Chem,2008,60.6LI S,LI X,ZHU Z.On tricyclic graphs with minimalenergy J.Match Commun.Math.Comput.Chem,2008,59.7SCIRIHA I,GUTMAN I.On the nullity of line graphsof treesJ.Discrete Math,2001,232:35-45.8ZHOU Q,WONG D,SUN D.An upper bound of the nullityof a graph in terms of order and maximum degree J.Linear Algebra Appl,2018,555:314-320.9SONG Y,SONG X,TAM B.A characterization ofgraphs with nullity IV(G)I-2m(G)+2c(G)J.Linear Algebra Appl,2015,465:363-375.(下转46 1页)455.第4期Hosoya指数Merrifield-Simmons指数的期望值的具体推导解析公式,并分别讨论了m(G,)和i（G,)的期望值，它们的组成和结构也正在向图论的相关研究方向发展.参考文献：1 ANDRIATINAN.Hosoys index and Merrifield-Simmonsindex of trees with prescribed degree sequence J.Discret Appl Math.2013,161:724-741.2ALI A,FURTULA B,GUTMAN I,et al.Augmentedzagreb index:Extremal results and bounds J.MATCH Commun.Math.Comput.Chem.2021,85:211-244.3马丽，苏苗苗，苗芸，等.多环链的Hosoya多项式J.科技风,2 0 19(4):33-35.4唐保祥，任韩.两类图完美匹配的计数公式J.吉林大学学报：理学版,2 0 16,54（4）：7 9 0-7 9 2.5 DENG H.Wiener indices of spiro and polyphenylhexagonal chains J.Mathematical and ComputerModelling,2011,55(3):634-644.6苏晓海，孙泽清，俞天仕，等.两类图族的Merrifield-Simmons指标J.安徽大学学报：自然科学版，2 0 2 2，46(1):32-36.7王守中，江蓉.三角系统T_n的匹配数与点独立集数J.西南师范大学学报：自然科学版，2 0 10,35(1):19-22.孙玉霜，等：随机七边形链中两类拓扑指数的期望值研究(2):550-562.12LIU Y,ZHUANG W,LIANG Z.Largest Hosoya index andsmallest Merrifield-Simmons index in tricyclicgraphs J.MATCH Commun Math Comput Chem.,2015,73(1):195-224.13CRUZ R,RADA J.Extremal graphs for exponentialsVDB indicesJ.Kragujevac J.Math.,2022,46:105-113.14HAFEEZ S,FAROOQ R.On generalized inverse sumindeg index and energy of graphs J.AIMS Math.,2020,5(3):2388-2411.15 ZHU Z,YUAN C,ANDRIANTIANA E,et al.Graphswith maximal Hosoya index and minimal Merrifield-Simmons index J.D i s c r e t M a t h.，2 0 14,32 9:77 87.461.8肖正明.双星树的Merrifield-Simmons和Hosoya指数序J.湖南城市学院学报：自然科学版,2 0 0 7，（4）：50 59.9GUTMAN I,POLANSKY O E.Mathematical conceptsin organic chemistry M.Berlin:Springer,1986.10 索郎王青，田双亮，杨青.特殊树的冠积的Merrifield-Simmons指标和Hosoya指标J.鲁东大学学报：自然科学版,2 0 2 0,36（1）：2 4-2 7.11HUANG,KUANG,DENG.The expect values of Hosoyaindex and Merrifield-Simmons index in a randompolyphenylene chain J.J Comb Optim.,2016,3(上接455页）10WANG L,WONG D.Bounds for the matchingnumber，t h e e d g e c h r o m a t i c n u m b e r a n d t h eindependence number of a graph in terms of rank J.Disc.Appl.Math,2014,166:276-281.11 MA X,WONG D,TIAN F.Nullity of a graph in termsof the dimension of cycle space and the number ofpendent vertices J.Disc Appl Math,2016,215:171-176.12 李鑫图的零度与独立数、悬挂点数关系的研究D.徐州：中国矿业大学，2 0 16.13CVETKOVIC D,GUTMAN I.The algebraic multiplicityof the number zero in the spectrum of a bipartite graphJ.Mat Vesnik(Beograd),1972,9:141-150.14WANG L.Nullity of a graph in terms of path covernumber J.Linear and Multilinear Algebra,2021,69(10):1902-1908.