无穷型双圈图的零度.pdf

2023年第3期（总第12 4期）牡丹江师范学院学报（自然科学版）Journal of Mudanjiang Normal UniversityNo.3,2023Total No.124文章编号：10 0 3-6 18 0(2 0 2 3)0 3-0 0 0 1-0 4无穷型双圈图的零度苗丰,王龙（安徽理工大学数学与大数据学院，安徽淮南2 32 0 0 1）摘要：无穷型双圈图(p,q,I)是通过连接两个不相交的圈C,和C的一个顶点与一条路径P,所得到的，其中,C,和C是圈长分别为p,的两个基本圈，路径P,的长度为l一1.图的零度n(G)是指图 G的邻接矩阵的0 特征值的重数，本文刻画了无穷型双圈图o(p,l)的零度，关键词：零度；无穷型双圈图；匹配数中图分类号O157.6The Nullity of Infinity-Type Bicyclic Graphs文献标志码AMIAO Feng,WANG Long(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan 232001,China)Abstract:The infinity-type bicyclic graph co(p,q,1)is obtained from two disjointed cyclesCpand C,by connecting one vertex of Cpand one vertex of C,with a path Pr,where C,andC,are the two basic cycles with cycle lengths of p and q respectively,and path P,has alength of I-1.The nullity of G,denoted by n(G),is the multiplicity of the eigenvalue ze-ro of the adjacency matrix of the graph G.This paper characterizes the nullity of the infini-ty-type bicyclic graphs.Key words:nullity;infinity-type bicyclic graphs;matching number在化学领域，图的零度问题有着重要且广泛的应用.在Hickel分子轨道模型中，若分子图G有n(G)0,则相应的化合物具有高度反应性和不稳定性,或不存在.1.2 1此外，图的零度在数学领域也意义重大，它和邻接矩阵A(G)的奇异性相关.若一个图的邻接矩阵A(G)是奇异的,那么这个图被称为奇异的，反之这个图被称为非奇异的.在这样的背景下，人们对图的零度的研究主要通过特定的图类着手进行.2 0 0 8 年袁西英3等人确定了所有n阶（n6)双圈图的零度集合是0,n一4.2 0 0 9年Guo4等收稿日期：2 0 2 3-0 3-0 9基金项目：中国博士后科学基金项目（2 0 19M660148）作者简介：苗丰（1998-），女，江苏淮安人.硕士研究生，主要从事图论研究；王龙（198 8-），男，安徽合肥人：副教授，博士，主要从事图论研究.2023年人刻画并给出了单圈图和匹配数之间的关系.2 0 16 年SaRula5等人刻画并给出了双圈图与匹配数之间的关系.本文考虑的图都是有限的、无向的和简单的.图G是一个具有n(G)个顶点和e(G)条边的连通图.图的基本圈数c(G)=e(G)一n(G)1,若c(G)=0,图G为一个树；若c(G)=1,图G为单圈图;若c(G)=2,图G为双圈图.图G的邻接矩阵记为A(G),它是一个n阶矩阵(a)n，当o,与u,邻接时,a,=1,否则,aj=0.邻接矩阵A(G)的0 特征值的重数称为图G的零度，图G的零度用n(G)来表示.显然，n(G)=n一r(A(G),这里的n为G的阶数，r(A(G)为A(G)的秩.G中的匹配是一组非相邻的边,如果M是匹配的,则与M的边相关的每个顶点都被M覆盖.完美匹配是覆盖G的每个顶点的匹配，最大匹配是覆盖图G中尽可能多的顶点的匹配.用m(G)来表示G的匹配数，也就是G的最大匹配的边数.本文刻画无穷型双圈图(p,q,l)的零度.1相关引理设G=（V,E)是一个n阶简单图，V(G)=u1,U2,)是图G的顶点集,E(G)=(e1,e2em)是图G的边集.(G)和e(G)分别代表图G的点数和边数.牡丹江师范学院学报（自然科学版）第3期C图1无穷型双圈图(p，q,l)C,和C,是圈长分别为p,q的两个基本圈，通过将两个不相交的圈C,和C,的一个顶点与一条路径P连接的连通图称作无穷型双圈图(p,q,l).其中，路径P,的长度为1一1.（图1).2016年Sa Rula4等人给出以下结果，从而决定了双圈图co(p,q,l)的零度与其匹配数之间的关系.引理15)在无穷型双圈图(p,q,)中,设GE(p,9,),则关于图G的零度与其匹配数之间的关系有以下结论：(1)n(G)一n(G)一2 m(G)一1当且仅当G满足以下任一条件：(i)p或q其中一个满足2(mod4),另一个为奇数,l是偶数；(i)p,q,l=1(mod2),p=q(mod4).(2)n(G)=n(G）一2 m(G）十1当且仅当p或q,其中一个满足0(mod4),另一个为奇数，l是奇数.（3）n(G)=n(G）一2 m(G)十2 当且仅当G满足以下任一条件：(i)p或q其中一个满足0(mod4),另一个满足2(mod4),l是偶数；(ii)p,q=0(mod4).（4）当G满足除以上三种情以外的其他情况时，n(G)=n(G)一2 m(G).引理2 6）在图G中，一条有四个度为2 的顶点的路径用一条边替代时,得到图H,则有n(G)=n(H)(图2）.22023年苗丰，等：无穷型双圈图的零度第3期V2XV4X图G图2 图G与图H(u1,U2U3,U4均是度为2 的顶点)22主要结果无穷型双圈图co(p,9,l)是通过将两个不相交的圈C,和C的一个顶点与一条路径P,连接所得到的双圈图,其中,C,和C是圈长分别为p,q的两个基本圈，路径P,的长度为1一1.首先，给出几个有限顶点的图的零度，可通过计算图的邻接矩阵特征值得到，也可以通过引理1导出引理3若GE(p,q,),其中,qE(3,4,5,6),1E(1,2,3,4,5),则其零度如表1所示与零度对应的特定无穷型双圈图7=0o(3,3,1)(5,6,1)(6,6,2)7=100(3,4,1)o(4,6,1)o(4,6,3)o(4,6,5)图H表1图的零度与其对应的特定无穷型双圈图零度(3,6,)o(3,5,2)00(6,6,4)(4,5,1)0(6,6,1)o(6,6,3)00(6,6,5)(5,5,1)0(3,5,4)(3,5,1)co(3,5,3)c(3,5,5)7=27=3引理4在无穷型双圈图co(p,q,l)中，p=4c+d,q=4e+f,1=4g+h，d,f E 3,4,5,6),h E(1,2,3,4,5),c,e,g为非负的整数.则有n(p,9,)=n(co(d,f,h),证明由引理2 知，在无穷型双圈图oo(p,9,L)中，1=4g十h,h=1,2,3,4,5,g为非负的整数时，有n(o(p,)=(c0(p,g,h).又由引理1知，在无穷型双圈图(p,q,l)中，在不同情况下，图的零度与匹配数之间的关系式为n(p,9,l)=n(c(p,q,)一2 m(p,9,)十a.其中,a的值是确定的,C,或C,的圈长每增加4c或4d,则匹配数随之增加2 c或2 d,零度不发生改变，即在无穷型双圈图(p,q,l)中，p=4c十d,q=4e十f,300(4,4,2)0o(4,6,4)(4,4,1)00(4,4,4)0(4,4,3)00(4,6,2)0(4,4,5)2023年c,e为非负的整数,n(p,q,)=n(d,f,L).综上,引理4得证.定理1在无穷型双圈图(p,q,l)中,设GE(p,q,l),则关于图G的特定零度与其对应的情况有以下结论：（1）n(G)=0 当且仅当G满足以下任一条件：(i)p+q 0(mod4),p,q 0(mod4);(i)p+q=0(mod4),且/=0(mod2).（2）n(G)=1当且仅当G满足以下任一条件：(i)p或q其中一个满足0(mod4),另一个满足1(mod2);(ii）p 或q其中一个满足0(mod4)，另一个满足0(mod2)，且l=1(mod2)；(ii)p,q 0(mod4),p+q=0(mod4),且/=1(mod2).（3）n(G)=2 当且仅当G满足以下任一条件：(i)p=q=0(mod4)且/=0(mod2);(ii)p或q其中一个满足0(mod4),另一个满足2(mod4),且/=0(mod2).(4)n(G)=3当且仅当p,q=0(mod4)且/=1(mod2).牡丹江师范学院学报（自然科学版）第3期证明充分性由引理1以及图的邻接矩阵秩的计算可得,对于任意特定的双圈图(p,9,l)的零度，可以通过引理1中p,9,I所满足的情况对应的关系式n(p,q,)=n(p,9,)2m(p,9,)+a得到.必要性由引理3和引理4可得，引理3描述了无穷型双圈图(p,q,l)的零度为0,1,2,3时其对应的特定无穷型双圈图，结合引理4,可以刻画出零度为0,1,2,3时所对应的所有无穷型双圈图(p,9,1)的特征,即p,q,I所满足的条件.参考文献1Atkins P,De Paula J.Physical ChemistryM.New York:Oxford University Press,2006.2Cvetkovic D M,Gutman I M.The algebraic multiplicity of the number zero in the spectrum of a bipartite graphJ.Mat Vesnik,1972(9):141-150.3袁西英，单海英，刘颖.双圈图的零度集合J.同济大学学报：自然科学版，2 0 0 8（0 3）：397-40 1.4JGuo JM,Yan W G,Yeh Y N.On the nullity and the matching number of unicyclic graphs JJ.Linear Algebra and its Applications,2009,431(8):1293-1301.5Sa Rula,A Chang,LI Jianxi.The nulity of bicyclic graphs in terms of their matching numberJ.Journal of Mathematical Research with Ap-plications,2016,36(6):12.6JWang L,Fang X,Geng X.Graphs with nullity 2c(G)+p(G)-1J.Discrete Mathematics,2022,345(5):112786.7彭杨，耿显亚，朱娜.几类正惯性指数为2 的图的刻画J.牡丹江师范学院学报：自然科学版，2 0 2 1（0 1）：1-6.8JChang S,Tam B S,Li J,et al.Graphs G with nullity 2c(G)+p(G)-1J.Discrete Applied Mathematics,2022,311:38-58.9姜娟，王龙.拟完全图的秩、正负惯性指数和零度J.牡丹江师范学院学报：自然科学版，2 0 2 1（0 3）：6-8 十13.1oMa X,Wong D,Tian F.Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices J.Discrete Applied Mathematics,2016,215:171-176.编辑：琳莉