完美非奇异图和完美奇异图
2023-06-13梁文君马晓玢
梁文君 马晓玢
摘 要:定义并确定了两种类型的图:当[n(≥2)]阶的连通图的所有[k(≥2)]阶连通诱导子图均为非奇异时,称其为完美非奇异图;当[n(≥3)]阶连通图的所有[k(≠2)]阶连通诱导子图均为奇异时,称其为完美奇异图.
关键词:奇异性;图的秩;邻接矩阵
[ 中图分类号 ]О157.6[ 文献标志码 ] A
Perfect Nonsingular Graphs and Perfect Singular Graphs
LIANG Wenjun,MA Xiaobin
(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan 232001,China)
Abstract:Two types of diagrams are defined and identified:A connected graph of order [n(≥2)] is called perfect nonsingular if all its connected induced subgraphs of order [k(≥2)] are nonsingular;A connected graph of order [n(≥3)]is called perfect singular if all its connected induced subgraphs of order [k(≠2)] are singular.
Key words:singularity;rank of graphs;adjacency matrixs
圖的奇异性在化学中体现于Hückel分子轨道模型,如果分子图是奇异的,那么相应的化合物是具有高度活性和不稳定性,或者说是不存在的.[1,2]1957年,Collatz 和 Sinogowitz[3]提出了刻画所有奇异图的问题.本文研究的是简单图.[A(G)=(aij)n×n]是图[G=(V(G),E(G))]的邻接矩阵,其中,若[vi]和[vj]间是邻接的,则[aij=aji=1];否则,[aij=0].[n]阶图[G]的秩,记为[r(G)],也是[A(G)]的秩.若[A(G)]是非奇异的,则[G]是非奇异的,[r(G)=n].同样地,若[A(G)]是奇异的,则[G]是奇异的,即[r(G) 1 预备知识 引理1 设[Kn]是[n]阶的完全图,则[Kn]是非奇异的,除非[n=1]. 引理2 设[Pn]是[n]阶的路径,则当且仅当[n]是偶数时[Pn]是非奇异的. 引理3 设[Cn]是[n]阶的圈,[Cn]是非奇异的,除非[n=0(mod4)]. 引理4 设[Km,n-m]是[n]阶的完全二部图,则[Km,n-m]是奇异的,除非[m=1]且[n=2]. Cvetkovi? 和 Gutman[1,4]证明,若[B]是一个二部的,且无长度为[0(mod4)]的圈,则[r(B)=2m(B)],其中[m(B)]是[B]的匹配数.这是引理2的一个推广,表明当且仅当[B]有一个完美匹配时,它是非奇异的.Guo[5]等确定了所有非奇异单圈图.Li[6]等刻画了深度为1的单圈图的线图的奇异性.尹慈[7]等对包含两个三角形的秩为7的双圈图进行了刻画,彭杨[8]等也对正惯性指数为2的树、单圈和双圈图进行了刻画.对于二部图[9]、双圈图[10]和三圈图[11],已确定了相应的秩集,但对非奇异图的刻画仍未确定.Chen[12]等也刻画了三种有向图的奇异性. 若[Φ=V(H)?V(G)]且[E(H)?E(G)],则图[H=(V(H),E(H))]称为图[G=(V(G),E(G))]的子图.从而,对于任意两个顶点[u,v∈V(H)],当且仅当[uv∈E(G)]时,[uv∈E(H)],那么,[H]称为[G]的诱导子图.因此,诱导子图是由其顶点集决定的.若[n(≥2)]阶连通图[G]的所有[k(≥2)]阶的连通诱导子图都是非奇异的,那么,[n(≥2)]阶的连通图[G]是完美非奇异的,1阶的图是奇异的.若当[n(≥3)]阶连通图所有[k(≠2)]阶的连通诱导子图都是奇异时,那么,[n(≥3)]阶连通图是完美奇异的,进一步得知2阶连通图是非奇异的. 本文确定了这两种类型的图,进一步定义了弱完美非奇异图和弱完美奇异图.如果[n(≥3)]阶的连通图的每个3阶连通诱导子图是非奇异的,则此连通图是弱完美非奇异的.如果每个[n(≥4)]阶连通图的3或4阶连通诱导子图是奇异的,则此连通图是弱完美奇异的. 定理1 设[G]是[n(≥5)]阶连通图:(i)[G]是弱完美非奇异图,当且仅当[G]是完美非奇异的或[G=Kn].(ii)[G]是弱完美奇异图,当且仅当[G]是完美奇异的或[G=Km,n-m]. 2 完美非奇异图 定理2 设[G]是[n(≥3)]阶连通图,则以下三项等价:(i)[G]是弱完美非奇异图.(ii)[G]是完美非奇异图.(iii)[G=Kn]. 证明 用(i)→(iii),(iii)→(ii)和(ii)→(i)来证明等价性.(ii)→(i)显而易见.需要注意的是,完全图的每一个连通诱导子图仍然是一个完全图,除非它的阶数为1,从而由引理1可得,它是非奇异的.(iii)→(ii)也得证. 而对于(i)→(iii),可以假设[G]是弱完美非奇异图且[V(G)=n≥3].若[n=3],那么[G=K3].再对[n]进行归纳.首先,假设[4≤n≤k]时[G]是一个完全图.再考虑[G]是弱完美非奇异图且[V(G)=k+1],则[G]包含一个[k]阶的弱完美非奇异诱导子图[H].根据归纳假设,有[H=Kk].如果将[v]表示为唯一的顶点,使得[v∈V(G)\V(Kk)],因为[G]是连通的,则[v]与某个顶点[x∈V(Kk)]相邻.若假设[G≠Kk+1],那么存在某个顶点[y∈V(Kk)],使得[y]在[G]中不与[v]相邻.现在[G]包含一个由顶点集[v,x,y]诱导出的3阶连通子图,它与[P3]同构,由引理2证明它是奇异的,与[G]是弱完美非奇异图矛盾.因此,[G=Kk+1],归纳完成. 定理的条件[n≥3]确保[G]至少包含一个3阶的子图,唯一的2阶连通图[K2]是完全非奇异的,得到推论1. 推论1 设[G]是[n(≥2)]阶连通图,则当且仅当[G=Kn]时,[G]是完美非奇异的. 3 完美奇异图 对于连通图[G],如果其所有3阶的连通诱导子图都是非奇异的,则[G]是非奇异的.如果所有3阶的连通诱导子图都是奇异的,[G]是可以为非奇异的.例如,任何偶数[n(≥4)]阶的路径[Pn]都是非奇异的,尽管其所有3阶的连通诱导子图都是奇异的.因此,当连通图的3阶或4阶诱导连通子图均为奇异时,定义该连通图为弱完美奇异. 定理3 设[G]为[n(≥4)]阶连通图.则以下三个条件是等价的:(i) [G]是弱完美奇异图.(ii)[G]是完美奇异图.(iii)[G=Km,n-m],其中[1≤m≤n-1]. 证明 用(i)→(iii),(iii)→(ii)和(ii)→(i)证明等价性.(ii)→(i)显而易见.当[G]是完全二部图时,它的每一个阶至少为2的连通诱导子图也是完全二部图,由引理4可得,[G]是奇异的除非阶为2,则(iii)→(ii)是可以确定的. 对于(i)→(iii),可以假设[G]是弱完美奇异图且[V(G)=n≥4].若[n=4],可见[C3]不是[G]的诱导子图,否则它包含一3阶的非奇异连通诱导子图,那么,有[G=C4=K2,2]或[G=P4].如果[G=P4],由引理2可得它是非奇异的,与假设的矛盾.因此[G=K2,2]. 当[n≥4]时,可以使用归纳法完成证明.首先,假设[4≤n≤k]时,[G=Km,n-m].再考虑一个[k+1(≥5)]阶的弱完美奇异图[G].根据归纳假设,[G]必包含了一个[k]阶的弱完美奇异图[H]作为它的诱导子图,即[Km,k-m].令[V(Km,k-m)=X?Y],其中[X={x1,x2,…,xm}]和[Y={y1,y2,…yk-m}]是两个划分集.设[v=V(G)\V(Km,k-m)],假设[vx1∈E(G)]不具有一般性,因为C3不包含在[G]中,那么对于任意[j]有[vyj?E(G)].进一步考虑,若当[2≤i≤m],[vxi?E(G)]时,那么由点集[v,x1,y1,xi]诱导出的一个连通诱导子图[P4]是非奇异的.这就意味着对于每一个[i],[vxi∈E(G)].因此[G=Km,k-m+1],归纳完成. 由引理2或引理4可得,[K2,1]也是奇异的,那么得出推论2. 推论2 设[G]是[n(≥3)]阶连通图.当[1≤m≤n-1]时,当且仅当[G=Km,n-m],G是完美奇异的. 参考文献 [1]D.Cvetkovi?,I.Gutman,N.Trinajstíc.Graph theory and molecular orbitals II[J].Croat.Chem.Acta.,44(1972),365-374. [2]E.Hückel.Quantentheoretische Beitr?ge zum Benzolproblem[J].Z.Phys.,70 (1931),204-286. [3]L.Collatz,U.Sinogowitz.Spektren endlicher Grafen[J].Abh.Math.Sem.Univ.Hamburg,21(1957),63-77. [4]D.Cvetkovi?,I.Gutman.The algebraic multiplicity of the number zero in the spectrum of a bipartite graph[J].Matematicki Vesnik,Beograd,9(1972),141-150. [5]J.Guo,W.Yan,Y.-N.Yeh.On the nullity and the matching number of unicyclic graphs[J].Linear Algebra Appl.,431(2009),1293-1301. [6]H.Li,Y.Fan,L.Su.On the nullity of the line graph of unicyclic graph with depth one[J].Linear Algebra Appl.,437(2012),2038-2055. [7]尹慈,马晓玢.包含两个三角形的秩为7的双圈图刻画[J].牡丹江师范学院学报:自然科学版,2021(3):1-5. [8]彭杨,耿显亚,朱娜.几类正惯性指数为2的图的刻画[J].牡丹江师范学院学报:自然科学版,2021(1):1-6. [9]Y.Fan,K.Qian.On the nullity of bipartite graphs[J].Linear Algebra Appl.,430(2009),2943-2949. [10]S.Hu,X.Tan,B.Liu.On the nullity of bicyclic graphs[J].Linear Algebra Appl.,429(2008),1387-1391. [11]B.Cheng,B.Liu.On the nullity of tricyclic graphs[J].Linear Algebra Appl.,434(2011),1799-1810. [12]X.Chen,J.Yang,X.Geng,L.Wang.Singularity of oriented graphs from several classes[J].B.AUST Math.Soc.,102(1)(2020),7-14. 編辑:琳莉