Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs

摘要

In 2001, Kawarabayashi proved that for any odd integer k ≥ 3, if a kconnected graph G is K_4~- -free, then G has a k-contractible edge. He pointed out, by a counterexample, that this result does not hold when k is even. In this paper, we have proved the following two results on the subject: (1) For any even integer k ≥ 4, if a k-connected graph G is K_4~--free and d_G(x) + d_G(y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. (2) Let t ≥ 3, k ≥ 2t - 1 be integers. If a k-connected graph G is (K_1 + (K_2 ∪ K_(1,t)))-free and d_G(x) + d_G(y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge.