不含某类子图的k-连通图中的一个结果

A result on k-connected graphs without a kind of subgraphs

如果将k-连通图G中的一条边收缩之后仍然得到一个k-连通图,则称这条边是G的一条k-可收缩边(简称可收缩边)。一个不含任何可收缩边的非完全k-连通图称为收缩临界k-连通图。2000年,Ando等证明了如下结论:设k≥4是一个整数,G是一个不含K-4的收缩临界k-连通图,则k是一个偶数,并且G中的每一个顶点都至少含在2个三角形中。文章进一步加强Ando等的结论,证明:设k≥3是一个整数,G是一个不含K-4的k-连通图,若G中存在至多含在一个三角形上的顶点,则每一个这样的顶点都关联一条k-可收缩边。

An edge of a k- connected graph is said to be k-contractible edge （simply contractible edge） if its contraction again results in a k connected graph. A non - complete k -connected graph without any contractible edges is called a contraction critical k-connected graph. In 2000, Ando et. al. proved the following result： Let k≥4 be an integer, G be a k-free contraction critical k-connected graph. Then k is even and every vertex in G is contained in at least two triangles. In this paper, we further strengthen the result of Ando et al. and prove the following result： Let k ≥3 be an integer, G be a k-free k-connected graph. If G contains some vertices such that every of them is contained in at most one triangle, then every of these vertices is incident with a k-contractible edge.