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

陈 洁,王 龙

(安徽理工大学 数学与大数据学院, 安徽 淮南 232000)

本文主要研究的是树的零度与路径覆盖数之间的关系,刻画了所有满足η(G)=ρ(G)的树.与Wang在文献[15]中描述的区别在于其刻画的是块都是圈和团组成的图,本文研究的是连通的无圈图的零度与路覆盖数之间的关系.

1 预备知识

本文研究的是无向的树,树是指任意两个顶点之间有且只有一条路径的无圈图.记简单无向图G的顶点集为V(G),边集为E(G).图G的邻接矩阵A(G)=(aij)n′n,其中若vi与vj相邻,则aij=1;否则aij=0.图G的秩定义为其邻接矩阵A(G)的秩,零度定义为其邻接矩阵A(G)零特征值的重数,分别用r(G),η(G)表示,两者之间存在等式r(G)+η(G)=|V(G)|.图的路覆盖是指图G中一组顶点不相交的诱导路(单个顶点的路径长为0)的集合,使G的每个顶点都是其中一条路的顶点,G的路覆盖数是指G的最小路覆盖,用ρ(G)表示.图G中点x的度表示与x相邻的边的数目,记作dG(x).若dG(x)=1,则点x表示图G的一个悬挂点.G中一条路P只有一个顶点与G中其他部分相连接,则称路P是图G的一个悬挂路.用G-U表示从图G中删去U的顶点及其相关联的边,其中U⊆V(G),若H是图G的诱导子图,直接用符号G-H表示.对于诱导子图H和H外一点x,顶点集V(H)∪{x}的G的诱导子图可记为H+x.用Pn表示有n个顶点的路.

下面给出本文结论证明中需要用到的一些重要引理.

引理1.1[14]:对一条路Pn,若n是奇数,则η(Pn)=1;若n是偶数,则η(Pn)=0.

引理1.2[14]:设G是包含一个悬挂点的图,图H是由G删去这个悬挂点及其相邻的点得到的诱导子图,则η(G)=η(H).

引理1.3[15]:设G是包含一个悬挂点的图,图H是由G删去这个悬挂点及其相邻的点得到的诱导子图,则ρ(H)≤ρ(G).

引理1.4[15]:若G是连通图,则η(G)≤ρ(G).

2 主要结果及证明

Wang[15]给出并证明了连通图G的零度与路覆盖数之间存在η(G)≤ρ(G)的关系,因此当G是树时,其零度和路径覆盖数之间也存在关系式η(G)≤ρ(G).下面我们来讨论在树中η(G)=ρ(G)成立的充分必要条件.首先给出了一些相关图、操作以及集合的定义.

图P:中心点a的度为p+r,有p+r条悬挂路P2s+1,其中r条悬挂路P2s+1上与中心点a相邻的顶点与一条P2s的悬挂点相连接(p≥2,r≥0).

操作A:对G中奇路上任意点与图P的中心点a相连,其中在悬挂点与图P相连时p≥1.

定义集合T:1)奇路P2n+1∈T;2)若图G∈T,对G进行操作A得到G′,则G′∈T.

在证明树中η(G)=ρ(G)成立的充分必要条件之前我们先给出一个引理及其证明.

引理2.1:若图G∈T,在G的非悬挂点上与P2n的一个悬挂点相连后得到G′,G′∉T则ρ(G′)=ρ(G)+1.

证明：G是路P2n+1时,ρ(G)=1.在P2n+1非悬挂点上与P2n的一个悬挂点相连得到G′,G′∉T,ρ(G′)=2.有ρ(G′)=ρ(G)+1.

若P′是图P中心点a的相邻点与P2n的一个悬挂点连接时得到的图,此时,P′∈T,则是在图P(除去中心点a的相邻点和悬挂点)上与P2n的一个悬挂点相连得到,则ρ(P′)=p-1+r+1=p+r.

若G是由路P2n+1经过n次操作A得到,G′是在图G的非悬挂点上与P2n的一个悬挂点相连得到,G′∉T.用归纳法来证明.

n=1时,ρ(G)=1+ρ(P)=1+p-1+r=p+r,ρ(G′)=1+ρ(P′)=1+p+r.有ρ(G′)=ρ(G)+1.

假设n=k时,ρ(G′)=ρ(G)+1成立.

下面来证明n=k+1时的情况.设B是由路P2n+1经过k次操作A得到,在B上经过1次操作A得到G,此时ρ(G)=ρ(B)+ρ(P)=ρ(B)+p-1+r.若G′是在第(k+1)次操作A中的图P(除去中心点a的相邻点和悬挂点)上与P2n连接得到,则ρ(G′)=ρ(B)+ρ(P′)=ρ(B)+p+r.若G′是在B中某个图P(除去中心点a的相邻点和悬挂点)上与P2n连接得到,则ρ(G′)=ρ(B+P2n)+ρ(P).又ρ(B+P2n)=ρ(B)+1,则ρ(G′)=ρ(B+P2n)+ρ(P)=ρ(B)+1+p-1+r=ρ(B)+p+r.有ρ(G′)=ρ(G)+1.

证毕.

定理2.2:若G是树,η(H)=ρ(G)当且仅当G∈T.

证明：首先证明充分性.若G是路P2n+1,η(G)=1,ρ(G)=1.则η(G)=ρ(G).

若G是由路P2n+1经过n次操作A得到,用归纳法来证明.

n=1时,G是由路P2n+1经过一次操作A后得到时,设x是图P中p条悬挂路P2s+1上的一个悬挂点,y是与x相邻唯一顶点,令H=G-x-y.根据引理1.2,η(H)=η(G),经过(s+1)次操作后,得到一条奇路P2n+1,p-1条路P2s+1和r条奇路,则η(G)=η(P2n+1)+(p-1)η(P2s+1)+r=p+r.又ρ(G)=1+p-1+r=p+r,则η(G)=ρ(G).

假设n=k时,η(G)=ρ(G)成立.

下面来证明n=k+1时的情况.设B是由路P2n+1经过k次操作A得到,在B上经过1次操作A得到G.B中奇路上任意点与图P相连后,设x是图P中p条悬挂路P2s+1上的任意一个悬挂点,y是与x相邻唯一顶点,令H=G-x-y.根据引理1.2,η(H)=η(G),经过(s+1)次操作后,得到图B和(p-1)条路P2s+1和r条奇路,则

η(G)=η(B)+(p-1)η(P2s+1)+r=η(B)+p-1+r

又ρ(G)=ρ(B)+p-1+r,且η(B)=ρ(B),则η(G)=ρ(G).

必要性:根据引理1.4,对图G,都有η(G)≤ρ(G).假设G∉T,证明其都满足η(G)<ρ(G)即可.设x是G的一个垂点,y是与x相邻的唯一顶点,令H=G-x-y,要证明η(G)<ρ(G).此时H可分为两种情况:

情况1:H∉T,由引理1.2,得到η(H)=η(G),由引理1.3得到ρ(H)≤ρ(G).对G的顶点进行归纳,K2∉T,利用数学归纳法,由于H=G-K2是G的子图,假设η(H)<ρ(H),则

η(G)=η(H)<ρ(H)≤ρ(G)

情况2:H∈T,则G是在H中除了悬挂点的任意顶点上连接一个路P2得到的图,设x是路P2与H相连后的路P2上的悬挂点,y是与x相邻唯一顶点,令H=G-x-y,根据引理1.2,η(H)=η(G).又根据充分性中证明有η(H)=ρ(H),则η(G)=ρ(H).根据引理2.1,此时ρ(G)=ρ(H)+1,则η(G)<ρ(G).

证毕.