# Structural Properties of Recursively Partitionable Graphs with Connectivity 2

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

top

## Abstract

top
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.

## How to cite

top

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 -

## NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.