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

Opuscula Mathematica

Recursively arbitrarily vertex-decomposable graphs

Olivier Baudon
Frédéric Gilbert
Mariusz Woźniak

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.

Full text (pdf)

• Olivier Baudon
• Univ. Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France
• CNRS, LaBRI, UMR 5800, F-33400 Talence, France
• Frédéric Gilbert
• Univ. Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France
• CNRS, LaBRI, UMR 5800, F-33400 Talence, France
• Mariusz Woźniak
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Krakow, Poland
• Revised: 2012-02-08.
• Accepted: 2012-02-09.