关于2树子图的一些性质

曾德炎，翟冬阳

(三亚学院 理工学院，海南 三亚 572022)

1 2树子图

用Km，Km,n，Pk分别表示顶点数为m的完全图，m×n阶完全二部图，顶点数为k的路。设v∈V(G),X⊆V(G)，用G[X]和NX(v)分别表示在G中由点集X诱导的子图和顶点v在点集X中的所有邻点构成的集合。记G-v=G[V(G)/v]，G-X=G[V(G)/X]。文中未定义的标记参见文献[1]。

图1 7阶2树星图T(7)Fig.1 7 vertices 2-tree star map T(7)

若n≥3，定义F(n)是在F(n-1)的基础上增加一个新的点xn，并且连接xn-2xn,xn-1xn。显然F(n)也是一个n个顶点的2树，可以称它为2路。图2是F(7)。

图2 7阶2树F(7)Fig.2 7 vertices 2-tree F(7)

主要证明了下面两个定理：

定理1：设G是一个顶点数为n的2树，设X⊆V(G)，其中|X|=k，3≤k≤n-1，则G中由顶点集X诱导的子图是某个顶点数为k的2树G1的子图。

对于k=n-1的情形，不仅证明了G1的存在性，并且找出了G1。

定理2： 设G是一个顶点数为n的2树，设xy∈C(G)，其中xy被s个耳朵z,z1,…,zs-1粘贴。若n≥6，则G中由顶点集V(G)/{x,y,z}诱导的子图是某个顶点数为n-3的2树的生成子图。若n≥8，则G中由顶点集V(G)/{x,y,z}诱导的子图是某个顶点数为n-3的2树T的生成子图，并且T≠T(n-3)。

2 证明

为证明定理1和定理2，用到以下已知结论：

定理3[2]：设G是一个顶点数为n的2树。则：

(1)G中至少有两个耳朵；

(2)G中度为2的顶点是G的耳朵；

(3)G中不存在两个耳朵相邻，除非G=K3；

(4)G中不包含长度至少为4的无弦圈；

(5)G是一个2连通图。

定理4[3]：G中的每一条边都可作为基础，通过反复粘贴耳朵将G构造。

通过定理4，能很快构造出4个顶点2树且只有K4-e，也就是T(4)，如图3。

图3 唯一的4阶2树K4-eFig.3 Only 4 vertices 2-tree K4-e

5个顶点2树只有两个，分别是K5-K3和K5-P4。由于K5-K3=T(5)，因此K5-P4是唯一一个非星图的5阶2树。图4是K5-K3，图5是K5-P4。

图4 5阶2树K5-K3Fig.4 5 vertices 2-tree K5-K3

图5 5阶2树K5-P4Fig.5 5 vertices 2-tree K5-P4

同样的方法，构造出6个顶点的2树有5个，7个顶点的2树有12个。对于7个顶点的2树，有一些很易证明的性质:设G的一个顶点数为7的2树，则在G中能找到两个点x,y，使得G-{x,y}是P5的子图；……