Structural properties of recursively partitionable graphs with connectivity 2
Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika Pilśniak · Discussiones Mathematicae Graph Theory · 2016
A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (nSome 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 Full PDF DMGT Pagethe 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.