Opuscula Math. 32, no. 4 (), 689-706
http://dx.doi.org/10.7494/OpMath.2012.32.4.689
Opuscula Mathematica

# 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.
Keywords: arbitrary vertex decomposable (AVD) graph, recursively AVD graphs.
Mathematics Subject Classification: 05C99, 68R10.