Dense Arbitrarily Vertex Decomposable Graphs
Mirko Horňák, Antoni Marczyk, Ingo Schiermeyer, Mariusz Woźniak · Graphs and Combinatorics · 2011
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 + · · · + n k = n there exists a partition (V 1, . . . , V k ) of the vertex set of G such that for each $${i \in \{1,\ldots,k\}}$$ , 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 ≥ 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.