Connectivity and tree structure in finite graphs

DOI10.1007/S00493-014-2898-5MaRDI QIDQ397061zbMATH OpenOpenAlexFDO

Authors Johannes Carmesin, Reinhard Diestel, F. Hundertmark, Maya Stein

Publication date 14 August 2014

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.1611, http://hdl.handle.net/10533/128272

zbMATH Keywords

graph connectivitygraph decompositiontree decomposition

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Graph minors (05C83)

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.

Review text

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.

Recommendations

• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.
• Canonical tree-decompositions of a graph that display its k-blocks
• Profiles of separations: in graphs, matroids, and beyond
• Canonical tree-decompositions of finite graphs. II. Essential parts
• \(k\)-blocks: a connectivity invariant for graphs

Cites work

• \(k\)-blocks: a connectivity invariant for graphs
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Cutting up graphs
• Graph minors. X: Obstructions to tree-decomposition
• Graph theory
• Highly connected sets and the excluded grid theorem
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• Vertex cuts
• Über n-fach zusammenhängende Eckenmengen in Graphen

Cited in

(27)

• Tangle-tree duality in abstract separation systems
• Trees of tangles in abstract separation systems
• Structural submodularity and tangles in abstract separation systems
• Acyclic, connected and tree sets
• Abstract separation systems
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Canonical trees of tree-decompositions
• Splitting groups with cubic Cayley graphs of connectivity two
• Vertex cuts
• Connecting Vertices by Independent Trees
• scientific article; zbMATH DE number 3861202 (Why is no real title available?)
• Canonical tree-decompositions of a graph that display its k-blocks
• On the block number of graphs
• Minimum bisection is fixed-parameter tractable
• scientific article; zbMATH DE number 4114654 (Why is no real title available?)
• Connectivity and Diagnosability of Leaf-Sort Graphs
• Trees of tangles in infinite separation systems
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Duality theorems for blocks and tangles in graphs
• Refining a tree-decomposition which distinguishes tangles
• Computing with tangles
• Packing cycles in undirected group-labelled graphs
• On the Connectivity of Token Graphs of Trees
• Efficiently distinguishing all tangles in locally finite graphs
• A note on the structure of locally finite planar quasi-transitive graphs
• Characterising 4-tangles through a connectivity property
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.

This page was built for publication: Connectivity and tree structure in finite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q397061)