×

zbMATH — the first resource for mathematics

Tree width and tangles: A new connectivity measure and some applications. (English) Zbl 0895.05034
Bailey, R. A. (ed.), Surveys in combinatorics, 1997. Proceedings of the 16th British combinatorial conference, London, UK, July 1997. London: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 241, 87-162 (1997).
N. Robertson and P. D. Seymour [J. Algorithms 7, 309-322 (1986; Zbl 0611.05017), or J. Comb. Theory, Ser. B 48, No. 2, 227-254 (1990; Zbl 0719.05032)] developed the theory of tree decomposition of graphs and introduced the tree width, a connectivity invariant of graphs (mostly of infinite type) focussing on global properties of graphs.
The author discusses a new connectivity invariant, the bramble number, of a graph \(G\). A bramble is a set of connected subgraphs of \(G\), any two of which intersect or are joined by an edge. Then the order of a bramble \(\beta\) is the minimum cardinality of a set of vertices which intersects every element of \(\beta\). The bramble number \(\text{BN} (G)\) of \(G\) is the maximum of the orders of its brambles.
For any graph \(G\), the tree width of \(G\) is equal to \(\text{BN} (G)-1\), see also P. D. Seymour and R. Thomas [J. Comb. Theory, Ser. B 58, No. 1, 22-23 (1993; Zbl 0795.05110)]. Besides the proof of this theorem, the author examines also the structure of graphs with large bramble numbers and resolves many questions on such graphs.
For the entire collection see [Zbl 0869.00029].
Reviewer: M.Hager (Leonberg)

MSC:
05C40 Connectivity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDF BibTeX XML Cite