Dense Arbitrarily Vertex Decomposable Graphs

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n (1), . . . , n (k) ) of positive integers such that n (1) + center dot center dot center dot + n (k) = n there exists a partition (V (1), . . . , V (k) ) of the vertex set of G such that for each , V (i) induces a connected subgraph of G on n (i) vertices. The main result of the paper reads as follows. Suppose that G is a connected graph on n a parts per thousand yen 20 vertices that admits a perfect matching or a matching omitting exactly one vertex. If the degree sum of any pair of nonadjacent vertices is at least n - 5, then G is arbitrarily vertex decomposable. We also describe 2-connected arbitrarily vertex decomposable graphs that satisfy a similar degree sum condition.