极小k-连通图中的k-可收缩边

k-Contractible Edge in Minimally k-Connected Graph

Ando证明了如果G是极小的k-连通图,且G中不含有K1+C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任一k度点x,都存在与x关联的不在三边形中的边,那么G中有k-可收缩边.

Ando proved that in a minimally k - connected graph G which does not contain a K1 ＋ C4, if for any vertex x ∈ V（G） of degree k, there exists and edge incident with x which is not contained any triangle, then G has a k - contractible edge. In this paper we obtain the result： ： in aminimally k - connected graph G which does not contain a P , if for any vertex x ∈ V（G） of degree k. There exists an edge incident with x which is not contained in any triangle, then G has a k -contractible edge.