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 conditions under 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 tree-decomposition 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\"on 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.
Original language | English |
---|---|
Pages (from-to) | 11-46 |
Journal | Combinatorica |
Volume | 34 |
Issue number | 1 |
Early online date | 30 Jan 2014 |
DOIs | |
Publication status | Published - 1 Feb 2014 |
Bibliographical note
31 pagesKeywords
- math.CO
- 05C40, 05C05, 05C83
- G.2.2