Connectivity and tree structure in finite graphs

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ö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.

31 pages

References in corpus (1)

• Profiles of separations: in graphs, matroids and beyond

Cited by in corpus (14)

• Tangle-tree duality in abstract separation systems
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Splitting groups with cubic Cayley graphs of connectivity two
• Triangulations of simplices with vanishing local h-polynomial
• Abstract Separation Systems
• Profiles of separations: in graphs, matroids and beyond
• Trees of tangles in abstract separation systems
• Trees of tangles in infinite separation systems
• Packing cycles in undirected group-labelled graphs
• Unifying duality theorems for width parameters in graphs and matroids. II. General duality
• On the Medianwidth of Graphs
• Efficiently distinguishing all tangles in locally finite graphs
• Edge-connectivity and tree-structure in finite and infinite graphs
• Agile Sets in Graphs