关键词: 拟k-连通图, 连通分支

Abstract:

Let G be a k-connected graph, and T be a k-vertex-cut of a k-connected graph G. If G-T can be partitioned into subgraphs G₁ and G₂ such that |G₁| ≥ 2, |G₂| ≥ 2, then we call T a nontrivial k-vertex-cut of G. Suppose that G is a (k-1)-connected graph without nontrivial (k-1)-vertex-cut, then we call G a quasi k-connected graph. In this paper, we prove that for any integer k ≥ 5 and t> $ \frac{k}{2}$, if G is a (K₂+tK₁)-free k-connected graph for which d (v)+d (w)≥ $\frac{{3k}}{2} $+t for any pair v, w of distinct vertices of G, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least $\frac{{\left| {V\left( G \right)} \right|}}{2} $ edges of G such that the contraction of every member of the results in a quasi k-connected graph.

Key words: quasi k-connected graph, component