- Tytuł:
- Structural Properties of Recursively Partitionable Graphs with Connectivity 2
- Autorzy:
-
Baudon, Olivier
Bensmail, Julien
Foucaud, Florent
Pilśniak, Monika - Tematy:
-
online arbitrarily partitionable graph
recursively arbitrarily partitionable graph
graph with connectivity 2
balloon graph - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/31342171.pdf Link otwiera się w nowym oknie
- Opis:
- 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł