含割边的图的零维数

钱克仕，李小新

（池州学院 数学计算机科学系，安徽 池州 247000）

含割边的图的零维数

钱克仕，李小新

（池州学院 数学计算机科学系，安徽 池州 247000）

图的零维数定义为图的零特征值的重数.本文讨论含割边的图的零维数,给出了该类图的零维数集,并刻画了零维数达到极大时的图结构.

图;邻接矩阵;谱;零维数;割边

1 引言

设G是n阶简单图,图G的邻接矩阵A(G)是一个n×n阶对称矩阵[aij],其中当顶点与顶点相邻时,aij= 1当顶点vi与顶点vj不相邻时,aij=0.称A(G)的特征值为图G的特征值.图G的所有特征值构成的集合(多重集)称为图G的谱.在图G的谱中零特征值的重数称为G的零维数,记为η(G).如果η(G)=0,则称图G非奇异.令Gn为具有特定性质的n阶简单图构成的集合,我们称数集为的零维数集。

1957年,Collatz和Sinogowitz[1]在考虑分子结构稳定性的问题时首先提出关于图的奇异性刻画问题.这个问题无论在化学中还是在数学中都有很重要的意义.对于一个二部图G(对应于一个碳氢化合物的分子图)来说,η(G)＞0意味着这种图所代表的分子是不稳定的.而由矩阵知识易见η(G)＞0当且仅A(G)当奇异,这对数学本身的研究也很有意义.

目前,关于图的奇异性刻画问题尚未完全解决,仅局限于一些简单的情形,如树,单圈图,双圈图,含悬挂点的图,以及具有极端零维数的图刻画等.在文献[2]中树的零维数可通过极大匹配获得.谭学忠和柳伯镰[5]给出了n(≥5)阶单圈图的零维数集,即为并刻画了η(G)=n-4时的单圈图G,提出了关于非奇异单圈图的一个公开问题.李薇和常安在文献[6]中解决了这一问题.扈生彪[7]等给出了n(≥6)阶双圈图的零维数集,即为并刻画了极值情形.另外,文献[9]给出零维数为1的图的构造方法,文献[10]给出了非奇异无圈图及单圈图的另一种刻画.在近期的文献中,程波,柳伯濂[8]讨论了一般n阶图G的零维数达到n-2及n-3的情形,并探讨了给定顶点数与边数时图的零维数达到极大值的情形.进一步地,李书超[4]刻画了含悬挂点的阶图的零维数达到n-4与n-5的情形.

本文主要研究了含割边的图的零维数情况,给出了该类图的零维数集,并刻画了零维数达到极大时的图结构.

2 定义和引理

设G=(V,E)为简单图.对G中任一顶点v,dG(v)t和NG(v)分别表示v在G中的度与邻点集.用ω (G)来表示图G的连通分支数.设F是E(G)的一个子集,用G-F表示G在图中删去F中的边后所得到的图.设W是E(G)的一个子集,G-W表示在图G中删去W中的顶点以及所有与W中点关联的边所得到的图.若G中的一边e满足ω(G-e)＞ω(G)则称e是G的割边.若dG(v)=1,则v称为G的一个悬挂点,与v关联的边称为G的一条悬挂边.若图G不含边,则G称为空图.若G不是空图,显然有η(G)≤n-2.更多图的术语参看文献[3].

图1 引理2.1中的图G和H

引理2.1设图G为一个含有割边e=uw的简单图.删除点u,w以及它们关联的边,并把NG-e(u)中的每个顶点NG-e(w)和中的每个顶点连接,得到一个新图H,则η(G)=η(H).

证明:不失一般性,假设图G连通.则G的结构如图1(1)所示,其中,NG-e(u)=:U,NG-e(w)=:W.设x为G对应零特征值的一个特征向量,并设x(u)=α,x(w)=β,则根据特征向量方程

显然,悬挂边也是一条割边,因此,我们有引理2.2[2]设G为n阶简单图,u∈V(G)为中G的一个悬挂点,uv∈E(G)为对应的悬挂边,则η(G-u,｛ ｝v).

3 主要结果

引理3.1[2]设为阶简单图,G=G1+G2+…+Gt,其中G1、G2、Gt为G的t个连通分支.则(G);从而η(G)=n当且仅当为空图.

定理 3.2 设G为一个n阶含割边的连通图.则η(G)=n-2当且仅当G是一个星图.若不是星图,则η(G)≤n-4.

证明:设e为G的一条割边.由引理2.1,η(G) =η(H),其中H是通过删除割边e的两个端点并将中的顶点与中的顶点连接所得到的一个n-2阶图.由引理3.1,η(H)=n-2当且仅当是一个空图,当且仅当G是一个星图.若G不是星图,则H不是空图,从而η(G)=η(H)≤n-2-2=n-4.得证.

用Qn表示n所有阶含割边的图的集合.

定理5 Qn的零维数集为 ｛n-2,n-4,n-5…｝.

证明:对于Qn中任一含割边的图G,由定理4知 η(G)∈ ｛n-2,n-4,n-5…,,0｝对任意,n-k∈ ｛n-2,n-4,n-5…,,0｝, k∈ ｛n,n-1,5,4,2 ｝考虑图2中的含割边的图.当k为偶数时,由引理2.2,连续删去路的悬挂点及其关联的边（当k=2时不删）,其零维数不变,最终得到一个n-k-2阶的星图,其零维数为n-k.当k为奇数时（注意到k≠3）,由引理2.2连续删去路的悬挂点及其关联的边,其零维数不变,最终得到一个三角形和n-k个孤立点构成的图,由引理3.1其零维数为. n-k得证。

图2两类含割边的图,其中K为K≥2偶数时,K为奇数时K≥5

[1]Collatz L,Sinogowitz U.Spektren endlicher grafen[J].Abh. Math.Sere.Univ.Hamburg.1957,21：70-75．

[2]Cvetkovic D,Doob M,Sachs H.Spectra of Graphs[M].New York:Academic Press,1980.

[3]Bondy J A,Murty U S R.Graph Theory with Applications [M].London and Basingstoke:The Mac Millan Press,1976.

[4]Li S Ch.On the nullity of graphs with pendent vertices[J]. Linear Algebra Appl.,2008,429:1619-1628.

[5]Tan X Zh,Liu B L.On the nullity of unicyclic graphs[J]. Linear Algebra Appl.,2003,408:12-220.

[6]Li W,Chang An.Describing the nonsingular unicyclic graph [J].Jounal of Mathematical Study,2007,4:442-445.

[7]Hu S,Liu B L,Tan X Zh.On the nullity of bicyclic graphs [J].Linear Algebra Appl.,2008,429:1387-1391.

[8]Chen B,Liu B L.On the nullity of graphs[J].Electronic Journal of Linear Algebra,2007,16:60-67.

[9]Sciriha I.On the construction of graphs of nullity one[J]. Discret Math.,1998,181:193-211.

[10]Nath M,Sarma B K.On the null-spaces of acyclic and unicyclic singular graphs[J].Linear Algebra Appl.,2007,427:42-54.

[责任编辑：曹怀火]

0157

A

1674-1102（2010）03-0005-02

2010-03-30

安徽省教育厅自然科学研究项目(KJ2010B136)；池州学院引进研究生科研启动项目(2009RC011)。

钱克仕(1984—),男,安徽六安人,池州学院数学计算机科学系教师,硕士,研究方向为谱图理论及应用；李小新(1976—),男,安徽怀宁人,池州学院数学计算机科学系副教授,硕士,研究方向为代数图论。