Structural Properties of Recursively Partitionable Graphs with Connectivity 2

Olivier Baudon, et al. "Structural Properties of Recursively Partitionable Graphs with Connectivity 2." Discussiones Mathematicae Graph Theory 37.1 (2017): 89-115. <http://eudml.org/doc/288041>.

@article{OlivierBaudon2017,
abstract = {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.},
author = {Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika Pilśniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {online arbitrarily partitionable graph; recursively arbitrarily partitionable graph; graph with connectivity 2; balloon graph},
language = {eng},
number = {1},
pages = {89-115},
title = {Structural Properties of Recursively Partitionable Graphs with Connectivity 2},
url = {http://eudml.org/doc/288041},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Olivier Baudon
AU - Julien Bensmail
AU - Florent Foucaud
AU - Monika Pilśniak
TI - Structural Properties of Recursively Partitionable Graphs with Connectivity 2
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 89
EP - 115
AB - 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.
LA - eng
KW - online arbitrarily partitionable graph; recursively arbitrarily partitionable graph; graph with connectivity 2; balloon graph
UR - http://eudml.org/doc/288041
ER -