An Ore-type condition for arbitrarily vertex decomposable graphs

Let GG be a graph of order nn and rr, 1≤r≤n1≤r≤n, a fixed integer. GG is said to be rr-vertex decomposable if for each sequence (n1,…,nr)(n1,…,nr) of positive integers such that n1+⋯+nr=nn1+⋯+nr=n there exists a partition (V1,…,Vr)(V1,…,Vr) of the vertex set of GG such that for each i∈{1,…,r}i∈{1,…,r}, ViVi induces a connected subgraph of GG on nini vertices. GG is called arbitrarily vertex decomposable if it is rr-vertex decomposable for each r∈{1,…,n}r∈{1,…,n}.In this paper we show that if GG is a connected graph on nn vertices with the independence number at most ⌈n/2⌉⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3n−3, then GG is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers rr for which the graphs verifying the above degree-sum condition are not rr-vertex decomposable.