Szczegóły publikacji
Opis bibliograficzny
Structural properties of recursively partitionable graphs with connectivity 2 / Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika PILŚNIAK // Discussiones Mathematicae. Graph Theory ; ISSN 1234-3099. — 2017 — vol. 37 iss. 1, s. 89–115. — Bibliogr. s. 109, Abstr.
Autorzy (4)
- Baudon Olivier
- Bensmail Julien
- Foucaud Florent
- AGHPilśniak Monika
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 104688 |
|---|---|
| Data dodania do BaDAP | 2017-04-04 |
| Tekst źródłowy | URL |
| DOI | 10.7151/dmgt.1925 |
| Rok publikacji | 2017 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Discussiones Mathematicae, Graph Theory |
Abstract
A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n(1),...,n(p)) of vertical bar V(G)vertical bar there exists a partition (V-1,..,V-p) of V(G) such that each V-i induces a connected subgraph of G on mi 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.
