PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 1 | 89-115
Tytuł artykułu

Structural Properties of Recursively Partitionable Graphs with Connectivity 2

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
37
Numer
1
Strony
89-115
Opis fizyczny
Daty
wydano
2017-02-01
otrzymano
2014-10-09
poprawiono
2015-02-25
zaakceptowano
2015-02-25
online
2017-01-13
Twórcy
  • Université Bordeaux, LaBRI, UMR 5800, F-33400 Talence, ; CNRS, LaBRI, UMR 5800, F-33400 Talence,, olivier.baudon@labri.fr
  • Department of Discrete Mathematics, AGH University of Science and Technology, A. Mickiewicza 30, 30-059 Kraków,, pilsniak@agh.edu.pl
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1925
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.