Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.7151/dmgt.1925 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
online arbitrarily partitionable graph,recursively arbitrarily partitionable graph,graph with connectivity 2,balloon graph | Discrete mathematics,Combinatorics,Graph toughness,Modular decomposition,Line graph,Bound graph,Graph power,Algebraic connectivity,Distance-hereditary graph,Symmetric graph,Mathematics | Journal |
Volume | Issue | ISSN |
37 | 1 | 1234-3099 |
Citations | PageRank | References |
1 | 0.35 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olivier Baudon | 1 | 60 | 10.38 |
| Julien Bensmail | 2 | 69 | 18.43 |
| Florent Foucaud | 3 | 122 | 19.58 |
| Monika Pilsniak | 4 | 29 | 5.42 |