A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition of G must not only be connected but also fulfil additional conditions. In this paper, we point out some structural properties of OL-AP and R-AP graphs with connectivity 2. In particular, we show that deleting a cut pair of these graphs results in a graph with a bounded number of components, some of whom have a small number of vertices. We obtain these results by studying a simple class of 2-connected graphs called balloons.
@article{bwmeta1.element.doi-10_7151_dmgt_1925,
author = {Olivier Baudon and Julien Bensmail and Florent Foucaud and Monika Pil\'sniak},
title = {Structural Properties of Recursively Partitionable Graphs with Connectivity 2},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {89-115},
zbl = {06676789},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1925}
}
Olivier Baudon; Julien Bensmail; Florent Foucaud; Monika Pilśniak. Structural Properties of Recursively Partitionable Graphs with Connectivity 2. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 89-115. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1925/