Recursively arbitrarily vertex-decomposable graphs

Abstract

A graph $G=(V,E)$ is arbitrarily vertex decomposable if for any sequence $\tau$ of positive integers adding up to $|V|$, there is a sequence of vertex-disjoint subsets of $V$ whose orders are given by $\tau$, and which induce connected graphs. The main aim of this paper is to study the recursive version of this problem. We present a solution for trees, suns, and partially for a class of 2-connected graphs called balloons.