2树的独立数

海南省三亚市学院理工学院 翟冬阳

一、介绍

本文所研究的图都是简单有限图。设G是一个图，E(G)和V（G）分别表示G的边集和顶点集。设表示由X诱导的子图，Gx和GX分别表示由诱导的子图，表示x的邻点集。我们用表示阶完全图，表示的补图，“+”表示两个图的交。本文未注释的标记参考[1]。

图是2树当且仅当G=K3，或者G中存在一个度为2的点v，使得与v相邻的两个点也相邻，且Gv是一个2树。我们把2树中度为2的点称为耳朵，显然，一个2树至少有两个耳朵。关于2树还有下面的性质：

二、证明

为了证明定理1.1，我们首先证明下面的引理：

[1] Bondy J A, Murty U S R． Graph Theory with Application[M]．London and Basingstoke： The Macmillan Press Ltd，1976．