A result on quasi k-connected graphs

作者：Yang Ying-qiu^*

来源：Applied Mathematics-A Journal of Chinese Universities Series B, 2015, 30(2): 245-252.

DOI：10.1007/s11766-015-3057-5

• 4-CONNECTED GRAPHS
• EDGES

Let G be a k-connected graph, and T be a subset of V (G). If G-T is not connected, then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with |T| = k. Let T be a k-cut-set of a k-connected graph G. If G - T can be partitioned into subgraphs G (1) and G (2) such that |G (1)| a parts per thousand yen 2, |G (2)| a parts per thousand yen 2, then we call T a nontrivial k-cut-set of G. Suppose that G is a (k -1)-connected graph without nontrivial (k -1)-cut-set. Then we call G a quasi k-connected graph. In this paper, we prove that for any integer k a parts per thousand yen 5, if G is a k-connected graph without K (-) (4), then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least edges of G such that the contraction of every member of them results in a quasi k-connected graph.

• 出版日期2015-6
• 单位安顺学院; 北京理工大学