陈 洁,王 龙

(安徽理工大学 数学与大数据学院, 安徽 淮南 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删去这个悬……