# Structural Properties of Recursively Partitionable Graphs with Connectivity 2

Olivier Baudon; Julien Bensmail; Florent Foucaud; Monika Pilśniak

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 1, page 89-115
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topOlivier 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.