An Ore-type condition for arbitrarily vertex decomposable graphs

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a1,…,ak) of positive integers such that a1+…+ak=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 ai vertices. In this paper we show that if G is a 2-connected graph of order n 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 a similar result for connected graphs satisfying a similar condition where n−3 is replaced by n−2.