×

zbMATH — the first resource for mathematics

Graph searching and a min-max theorem for tree-width. (English) Zbl 0795.05110
Summary: The tree-width of a graph \(G\) is the minimum \(k\) such that \(G\) may be decomposed into a “tree-structure” of pieces each with at most \(k+1\) vertices. We prove that this equals the maximum \(k\) such that there is a collection of connected subgraphs, pairwise intersecting or adjacent, such that no set of \(\leq k\) vertices meets all of them. A corollary is an analogue of LaPaugh’s “monotone search” theorem for cops trapping a roober they can see (LaPaugh’s robber was invisible).

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
91A43 Games involving graphs
PDF BibTeX XML Cite
Full Text: DOI