无穷型双圈图的零度

苗丰 王龙

文章编号：1003?6180（2023） 03?0001?04

摘  要：无穷型双圈图[∞p，q，l]是通过连接两个不相交的圈[Cp]和[Cq]的一个顶点与一条路径[Pl]所得到的，其中，[Cp]和[Cq]是圈长分别为[p]，[q]的两个基本圈，路径[Pl]的长度为[l-1].图的零度[ηG]是指图[G]的邻接矩阵的0特征值的重数.本文刻画了无穷型双圈图[∞p，q，l]的零度.

关键词：零度；无穷型双圈图；匹配数

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

The Nullity of Infinity-Type Bicyclic Graphs

MIAO Feng，WANG Long

（School of Mathematics and Big Data， Anhui University of Science and Technology，

Huainan 232001， China）

Abstract：The infinity-type bicyclic graph [∞p，q，l] is obtained from two disjointed cycles [Cp]and [Cq] by connecting one vertex of [Cp]and one vertex of [Cq] with a path [Pl]， where [Cp] and [Cq] are the two basic cycles with cycle lengths of [p] and [q] respectively， and path [Pl] has a length of [l-1]. The nullity of [G]， denoted by [ηG]， is the multiplicity of the eigenvalue zero of the adjacency matrix of the graph [G]. This paper characterizes the nullity of the infinity-type bicyclic graphs.

Key words： nullity； infinity-type bicyclic graphs； matching number

在化學领域，图的零度问题有着重要且广泛的应用.在Hückel分子轨道模型中，若分子图[G]有[ηG>0]，则相应的化合物具有高度反应性和不稳定性，或不存在.[1，2]此外，图的零度在数学领域也意义重大，它和邻接矩阵[AG]的奇异性相关.若一个图的邻接矩阵[AG]是奇异的，那么这个图被称为奇异的，反之这个图被称为非奇异的.在这样的背景下，人们对图的零度的研究主要通过特定的图类着手进行.2008年袁西英[3]等人确定了所有[n]阶（[n≥6]）双圈图的零度集合是[0， n-4].2009年Guo[4]等人刻画并给出了单圈图和匹配数之间的关系.2016年Sa Rula[5]等人刻画并给出了双圈图与匹配数之间的关系.本文考虑的图都是有限的、无向的和简单的.

图[G]是一个具有[nG]个顶点和[eG]条边的连通图.图的基本圈数[cG=eG-nG+1]，若[cG=0]，图[G]为一个树；若[cG=1]，图[G]为单圈图；若[cG=2]，图[G]为双圈图.图[G]的邻接矩阵记为[AG]，它是一个[n]阶矩阵[aijn×n]，当[vi]与[vj]邻接时，[aij=1]，否则，[aij=0].邻接矩阵[AG]的0特征值的重数称为图[G]的零度，图[G]的零度用[ηG]来表示.显然，[ηG=n-rAG]，这里的[n]为[G]的阶数，[rAG]为[AG]的秩.[G]中的匹配是一组非相邻的边，如果[M]是匹配的，则与[M]的边相关的每个顶点都被[M]覆盖.完美匹配是覆盖[G]的每个顶点的匹配，最大匹配是覆盖图[G]中尽可能多的顶点的匹配.用[mG]来表示[G]的匹配数，也就是[G]的最大匹配的边数.本文刻画无穷型双圈图[∞p，q，l]的零度.

1 相关引理

设[G=V，E]是一个[n]阶简单图，[VG=v1，v2…vn]是图[G]的顶点集，[EG=e1，e2…em]是图[G]的边集.[vG]和[eG]分别代表图[G]的点数和边数.

[Cp]和[Cq]是圈长分别为[p]，[q]的两个基本圈， 通过将两个不相交的圈[Cp]和[Cq]的一个顶点与一条路径[Pl]连接的连通图称作无穷型双圈图[∞p，q，l]. 其中，路径[Pl]的长度为[l-1].（图1）.

2016年Sa Rula[4]等人给出以下结果，从而决定了双圈图[∞p，q，l]的零度与其匹配数之间的关系.

引理1[5] 在无穷型双圈图[∞p，q，l]中，设[G∈∞p，q，l]，则关于图[G]的零度与其匹配数之间的关系有以下结论：

（1）[ηG][=][nG][-][2mG][-1]当且仅当[G]满足以下任一条件：

（i）[p]或[q]其中一个满足[2mod4]，另一个为奇数，[l]是偶数；

（ii）[p，q，l≡1mod2]，[p≡qmod4].

（2）[ηG=][nG-2mG+1]当且仅当[p]或[q]，其中一个满足[0mod4]，另一个为奇数，[l]是奇数.

（3） [ηG=nG-2mG+2]当且仅当[G]满足以下任一条件：

（i） [p]或[q]其中一个满足[0mod4]，另一个满足[2mod4]，[l]是偶数；

（ii） [p，q≡0mod4].

（4） 当[G]满足除以上三种情以外的其他情况时，[ηG=nG-2mG].

引理2[6] 在图[G]中，一条有四个度为2的顶点的路径用一条边替代时，得到图[H]，则有[ηG=ηH]（图2） .

2 主要结果

无穷型双圈图[∞p，q，l]是通过将两个不相交的圈[Cp]和[Cq]的一个顶点与一条路径[Pl]连接所得到的双圈图，其中，[Cp]和[Cq]是圈长分别为[p]，[q]的两个基本圈，路径[Pl]的长度为[l-1].

首先，给出几个有限顶点的图的零度，可通过计算图的邻接矩阵特征值得到，也可以通过引理1导出.

引理3 若[G∈∞p，q，l]，其中，[p，q∈3，4，5，6]，[l∈1，2，3，4，5]，则其零度如表1所示.

引理4 在无穷型双圈图[∞p，q，l]中，[p=][4c+d]，[q=][4e+f]，[l=][4g+h]，[d，f∈] [3，4，5，6]，[h∈1，2，3，4，5]，[c，e，g]为非负的整数.则有[η∞p，q，l=η∞d，f，h].

证明 由引理2知，在无穷型双圈图[∞p，q，l]中，[l=4g+h]，[h=1，2，3，4，5]，[g]为非负的整数时，有[η∞p，q，l=η∞p，q，h].

又由引理1知，在无穷型双圈图[∞p，q，l]中，在不同情况下，图的零度与匹配数之间的关系式为[η∞p，q，l=][n∞p，q，l][-2m∞p，q，l+a].其中，[a]的值是确定的，[Cp]或[Cq]的圈长每增加[4c]或[4d]，则匹配数随之增加[2c]或[2d]，零度不发生改变，即在无穷型双圈图[∞p，q，l]中，[p=4c+d]，[q=4e+f]，[c，e]为非负的整数，[η∞p，q，l=η∞d，f，l].综上，引理4得证.

定理1 在无穷型双圈图[∞p，q，l]中，设[G∈∞p，q，l]，则关于图[G]的特定零度与其对应的情况有以下结论：

（1） [ηG=0]当且仅当[G]满足以下任一条件：

（i）[p+q≠0mod4]，[p，q≠0mod4]；

（ii） [p+q=0mod4]，且[l=0mod2].

（2） [ηG=1]当且仅当[G]满足以下任一条件：

（i） [p]或[q]其中一个满足[0mod4]，另一个满足[1（mod2）]；

（ii） [p]或[q]其中一个满足[0mod4]，另一个满足[0（mod2）]，且[l=1mod2]；

（iii）[p，q≠0mod4]，[p+q=0mod4]，且[l=1mod2].

（3） [ηG=2]当且仅当[G]满足以下任一条件：

（i） [p≡q≡0mod4]且[l=0mod2]；

（ii）[p]或[q]其中一个满足[0mod4]，另一个满足[2mod4]，且[l=0mod2].

（4） [ηG=3]当且仅当[p，q≡0mod4]且[l≡1mod2].

证明 充分性由引理1以及图的邻接矩阵秩的计算可得，对于任意特定的双圈图[∞p，q，l]的零度，可以通过引理1中[p，q，l]所满足的情况对应的关系式[η∞p，q，l=n∞p，q，l-2m∞p，q，l+a]得到.

必要性由引理3和引理4可得，引理3描述了无穷型双圈图[∞p，q，l]的零度为[0，1，2，3]时其对应的特定无穷型双圈图，结合引理4，可以刻画出零度为[0，1，2，3]时所对应的所有无穷型双圈图[∞p，q，l]的特征，即[p，q，l]所满足的条件.

参考文献

[1]Atkins P， De Paula J. Physical Chemistry[M]. New York：Oxford University Press， 2006.

[2]Cvetkovi? D M ， Gutman I M . The algebraic multiplicity of the number zero in the spectrum of a bipartite graph[J]. Mat Vesnik， 1972（9）：141–150.

[3]袁西英，單海英，刘颖.双圈图的零度集合[J].同济大学学报：自然科学版，2008（03）：397-401.

[4]Guo J M， Yan W G， Yeh Y N. On the nullity and the matching number of unicyclic graphs[J]. Linear Algebra and its Applications， 2009， 431（8）：1293-1301.

[5]Sa Rula， A Chang， LI Jianxi. The nullity of bicyclic graphs in terms of their matching number[J]. Journal of Mathematical Research with Applications， 2016， 36（6）：12.

[6]Wang L， Fang X， Geng X. Graphs with nullity [2cG+pG-1][J]. Discrete Mathematics， 2022， 345（5）： 112786.

[7]彭杨，耿显亚，朱娜.几类正惯性指数为2的图的刻画[J].牡丹江师范学院学报：自然科学版，2021（01）：1-6.

[8]Chang S， Tam B S， Li J， et al. Graphs G with nullity [2cG+pG-1][J]. Discrete Applied Mathematics， 2022， 311： 38-58.

[9]姜娟，王龙.拟完全图的秩、正负惯性指数和零度[J].牡丹江师范学院学报：自然科学版，2021（03）：6-8+13.

[10]Ma 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.

编辑：琳莉