Connectivity and tree structure in finite graphs (Q397061)

Considering systems of separations in a graph \(G\) that separate every pair of a given set of vertex sets that are themselves not separated by these separations, the authors determine conditions under which such a separation system contains a nested subsystem that still separates those sets and is invariant under automorphisms of \(G\). As an application, it is shown that the \(k\)-blocks of a graph \(G\) live in distinct parts of a tree-decomposition of \(G\) of adhesion at most \(k\), whose decomposition tree is invariant under the automorphisms of \(G\). Under mild additional assumptions, these decompositions can be combined into one overall tree-decomposition that distinguishes all the \(k\)-blocks of a finite graph.