Connected tree-width

DOI10.1007/S00493-016-3516-5MaRDI QIDQ722321zbMATH OpenOpenAlexFDO

Authors Reinhard Diestel, Malte Müller

Publication date 23 July 2018

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

tree-decompositiontree-width

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40) Graph minors (05C83)

Abstract: The connected tree-width of a graph is the minimum width of a tree-decomposition whose parts induce connected subgraphs. Long cycles are examples of graphs that have small tree-width but large connected tree-width. We show that a graph has small connected tree-width if and only if it has small tree-width and contains no long geodesic cycle. We further prove a connected analogue of the duality theorem for tree-width: a finite graph has small connected tree-width if and only if it has no bramble whose connected covers are all large. Both these results are qualitative: the bounds are good but not tight. We show that graphs of connected tree-width $k$ are $k$-hyperbolic, which is tight, and that graphs of tree-width $k$ whose geodesic cycles all have length at most $ell$ are $lfloor3over2ell(k-1)floor$-hyperbolic. The existence of such a function $h(k,ell)$ had been conjectured by Sullivan.

Review text

The connected tree-width of a graph is the minimum width that a connected tree-decomposition of the graph can have. The authors prove that the connected tree-width of a graph is bounded above by a function of its tree-width and of the maximum length of its geodesic cycles. A bramble is a set of pairwise touching connected sets of vertices where two vertex sets touch if they share a vertex or the graph has an edge between them. A finite graph is shown to have small connected tree-width if and only if it has no bramble whose connected covers are large. Graphs of connected tree-width \(k\) are shown to be \(k\)-hyperbolic. If a graph has tree-width less than \(k\) and no geodesic cycle long than \(l\), and the graph is not a forest, then the tree-length of the graph is shown to be at most \(l(k-2)\).

Recommendations

• Bounding connected tree-width
• Tree-width of product of a connected graph and a k-connected partial k-tree
• scientific article; zbMATH DE number 1057879
• On the tree-width of planar graphs
• On tree width, bramble size, and expansion

Cites work

• A Menger-like property of tree-width: The finite case
• Bounding connected tree-width
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Graph searching and a min-max theorem for tree-width
• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• Tree-decompositions with bags of small diameter

Cited in

(17)

• Tree-length equals branch-length
• Combining restarts, nogoods and bag-connected decompositions for solving csps
• Introducing directed tree width
• scientific article; zbMATH DE number 3861202 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• FPT algorithms for embedding into low complexity graphic metrics
• Circumference and pathwidth of highly connected graphs
• Tree-width of product of a connected graph and a k-connected partial k-tree
• Bounding connected tree-width
• To approximate treewidth, use treelength!
• Tree decompositions and social graphs
• Results on hyperbolicity in graphs: a survey
• Connected search for a lazy robber
• Treewidth versus clique number. II: Tree-independence number
• Bounded-diameter tree-decompositions
• Strict self-assembly of discrete self-similar fractals in the abstract tile assembly model
• Quasi-linear distance query reconstruction for graphs of bounded treelength

This page was built for publication: Connected tree-width

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