k-blocks: a connectivity invariant for graphs

DOI10.1137/130923646MaRDI QIDQ5246089zbMATH OpenOpenAlexFDO

Authors Reinhard Diestel, Johannes Carmesin, Matthias Hamann, F. Hundertmark

Publication date 17 April 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-blockconnectivityglobaltangletree-decompositiontree-widthwidth parameter

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A $k$-block in a graph $G$ is a maximal set of at least $k$ vertices no two of which can be separated in $G$ by fewer than $k$ other vertices. The block number $$ of $G$ is the largest integer $k$ such that $G$ has a $k$-block. We investigate how $$ interacts with density invariants of graphs, such as their minimum or average degree. We further present algorithms that decide whether a graph has a $k$-block, or which find all its $k$-blocks. The connectivity invariant $$ has a dual width invariant, the block-width $mbw(G)$ of $G$. Our algorithms imply the duality theorem $$: a graph has a block-decomposition of width and adhesion $<k$ if and only if it contains no $k$-block.

Recommendations

• On the block number of graphs
• Blocks in \(k\)-connected graphs
• scientific article; zbMATH DE number 1960407
• On the structure of a k-connected graph
• Canonical tree-decompositions of a graph that display its k-blocks

Cited in

(18)

• A unified treatment of linked and lean tree-decompositions
• A Menger-like property of tree-cut width
• Characterising \(k\)-connected sets in infinite graphs
• Tangle-tree duality in abstract separation systems
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Blocks in \(k\)-connected graphs
• Packing A-paths of length zero modulo a prime
• Connectivity and tree structure in finite graphs
• scientific article; zbMATH DE number 4125432 (Why is no real title available?)
• On the block number of graphs
• scientific article; zbMATH DE number 205335 (Why is no real title available?)
• On Fault-Tolerant Low-Diameter Clusters in Graphs
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• A short derivation of the structure theorem for graphs with excluded topological minors
• Duality theorems for blocks and tangles in graphs
• Packing cycles in undirected group-labelled graphs
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.

This page was built for publication: \(k\)-blocks: a connectivity invariant for graphs

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