Vertex cuts

DOI10.1002/JGT.21844MaRDI QIDQ2947947zbMATH OpenOpenAlexFDO

Authors M. J. Dunwoody, B. Krön

Publication date 29 September 2015

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.0064

zbMATH Keywords

connectivity of graphsstructure trees

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40)

Abstract: We generalise structure tree theory, which is based on removing finitely many edges, to removing finitely many vertices. This gives a significant generalization of Tutte's tree decomposition of 2-connected graphs into 3-connected blocks. For a finite graph there is a structure tree that contains information about $k$-connectivity for any $k$. The theory can also be applied to infinite graphs that have more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a generalization of Stallings' structure theorem for groups with more than one end.

Recommendations

• On the structure of vertex cuts separating the ends of a graph
• Cutting up graphs revisited -- a short proof of Stallings' structure theorem.
• A cactus theorem for end cuts
• The tree of cuts and minimal \(k\)-connected graphs
• Some finiteness results concerning separation in graphs

Cites work

• A cactus theorem for end cuts
• An Analogue of the Torus Decomposition Theorem for Certain Poincaré Duality Groups
• Connectivity and tree structure in finite graphs
• Context-free groups and their structure trees.
• Cutting up graphs
• Cutting up graphs revisited -- a short proof of Stallings' structure theorem.
• Decomposing infinite 2-connected graphs into 3-connected components
• End compactifications in non-locally-finite graphs
• End-transitive graphs
• Ends of graphs. II
• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• Lattices of cuts in graphs
• Metric ends, fibers and automorphisms of graphs
• Neuaufbau der Endentheorie
• On torsion-free groups with infinitely many ends
• Quasi-isometries between non-locally-finite graphs and structure trees
• Some finiteness results concerning separation in graphs
• The algebraic torus theorem
• The classification of connected-homogeneous digraphs with more than one end
• The structure of locally finite two-connected graphs
• Topological groups and infinite graphs
• Transitivity conditions in infinite graphs
• Vertex-transitive graphs and accessibility
• Über die Enden diskreter Räume und Gruppen
• Über die Enden topologischer Räume und Gruppen

Cited in

(22)

• Some finiteness results concerning separation in graphs
• A tree-of-tangles theorem for infinite tangles
• On the structure of a 3-connected graph. II
• Transitivity conditions in infinite graphs
• Locally-finite connected-homogeneous digraphs
• The language of self-avoiding walks
• Canonical trees of tree-decompositions
• Cut for core logic
• Cutting up graphs revisited -- a short proof of Stallings' structure theorem.
• A descriptive construction of trees and Stallings' theorem
• Connectivity and tree structure in finite graphs
• The planar cubic Cayley graphs
• Trees of tangles in infinite separation systems
• Rational discrete first degree cohomology for totally disconnected locally compact groups
• Structure trees, networks and almost invariant sets
• A cactus theorem for end cuts
• Self-avoiding walks and multiple context-free languages
• On Whitehead's cut vertex lemma
• Can you tell a tree from its branches?
• Self-avoiding walk is ballistic on graphs with more than one end
• On the structure of vertex cuts separating the ends of a graph
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.

This page was built for publication: Vertex cuts

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