Characterization of k-subconnected graphs

Abstract In this paper, we give the definition of k-subconnected graphs. Let G be a graph with at least 3k − 1 vertices. Then G is called a k-subconnected graph if, for any 2k vertices of G, there are k disjoint paths in G joining them in pairs. We prove that G is a k-subconnected graph if and only if, for any cutset S ⊆ V(G) with |S| ≤ k − 1,  ω(G − S) ≤ |S| + 1, where ω(G) is the number of components of G.