Structural Properties of Recursively Partitionable Graphs with Connectivity 2

• Autorzy: Olivier Baudon , Julien Bensmail , Florent Foucaud , Monika Pilśniak
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

online arbitrarily partitionable graph; recursively arbitrarily partitionable graph; graph with connectivity 2; balloon graph

Kategorie tematyczne

• 68R10: Graph theory (including graph drawing)
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 89-115

Daty

wydano

2017-02-01

otrzymano

2014-10-09

poprawiono

2015-02-25

zaakceptowano

2015-02-25

online

2017-01-13

Twórcy

autor

Olivier Baudon

• Université Bordeaux, LaBRI, UMR 5800, F-33400 Talence, ; CNRS, LaBRI, UMR 5800, F-33400 Talence,

autor

Julien Bensmail

• Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby,

autor

Florent Foucaud

• LIMOS – CNRS UMR 6158, Université Blaise Pascal, Clermont-Ferrand,

autor

Monika Pilśniak

• Department of Discrete Mathematics, AGH University of Science and Technology, A. Mickiewicza 30, 30-059 Kraków,

Identyfikatory

DOI

10.7151/dmgt.1925