A note on Arbitrarily vertex decomposable graphs, Opuscula Mathematica 26

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,...,nk) of positive integers such that n1 +... + nk = n there exists a partition (V1,...,Vk) of the vertex set of G such that for each i ∈ {1,...,k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2 ⌉ and such that the degree sum of any pair of nonadjacent vertices is at least n − 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition where the bound n − 3 is replaced by n − 2.