A note on arbitrarily vertex decomposable graphs

Abstract

A graph $G$ of order n is said to be arbitrarily vertex decomposable if for each sequence $(n_{1},\ldots,n_{k})$ of positive integers such that $n_{1}+\ldots+n_{k}=n$ there exists a partition $(V_{1},\ldots,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. In this paper we show that if $G$ is a two-connected graph on n vertices with the independence number at most $\lceil n/2\rceil$ and such that the degree sum of any pair of non-adjacent vertices is at least $n-3$, then $G$ is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound $n-3$ is replaced by $n-2$.