An Ore-type condition for arbitrarily vertex decomposable graphs

A graph G of order n is called arbitrarily vertex decomposable if for each sequence ( a 1 , … , a k ) of positive integers such that a 1 + … + a k = n there exists a partition ( V 1 , … , V k ) of the vertex set of G such that for each i ∈ { 1 , … , k } , V i induces a connected subgraph of G on a i 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 .