Name
Abstract | ||
|---|---|---|
Considering systems of separations in a graph that separate every pair of a given set of vertex sets that are themselves not separated by these separations, we determine conditionsunder which such a separation system contains a nested subsystem that still separates those sets and is invariant under the automorphisms of the graph.As an application, we show that the k-blocks -- the maximal vertex sets that cannot be separated by at most k vertices -- of a graph G live in distinct parts of a suitable treedecomposition of G of adhesion at most k, whose decomposition tree is invariant under the automorphisms of G. This extends recent work of Dunwoody and Krön and, like theirs, generalizes a similar theorem of Tutte for k=2.Under mild additional assumptions, which are necessary, our decompositions can be combined into one overall tree-decomposition that distinguishes, for all k simultaneously, all the k-blocks of a finite graph. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00493-014-2898-5 | Combinatorica |
Keywords | Field | DocType |
05c05,05c40,05c83,tree decomposition,tree structure | Block graph,Discrete mathematics,Combinatorics,Tree-depth,Tree (graph theory),Vertex (graph theory),Tree decomposition,SPQR tree,Spanning tree,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
34 | 1 | Combinatorica 34 (2014), pp 11-46 |
Citations | PageRank | References |
7 | 0.74 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Carmesin | 1 | 29 | 7.08 |
| Reinhard Diestel | 2 | 452 | 68.24 |
| Fabian Hundertmark | 3 | 17 | 2.77 |
| maya stein | 4 | 81 | 15.65 |