Structural properties of recursively partitionable graphs with connectivity 2

Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika Pilsniak

Research output: Contribution to journalJournal articleResearchpeer-review

185 Downloads (Pure)

Abstract

A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1,..., np) of jV (G)j 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 con-nected but also ful_l 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.
Original languageEnglish
JournalDiscussiones Mathematicae. Graph Theory
Volume37
Pages (from-to)89–115
Number of pages27
ISSN1234-3099
DOIs
Publication statusPublished - 2017

Fingerprint Dive into the research topics of 'Structural properties of recursively partitionable graphs with connectivity 2'. Together they form a unique fingerprint.

Cite this