Treewidth of Cartesian products of highly connected graphs

DOI10.1002/JGT.21677MaRDI QIDQ5325943zbMATH OpenOpenAlexFDO

Authors David R. Wood

Publication date 31 July 2013

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

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

zbMATH Keywords

Cartesian producttreewidth

Mathematics Subject Classification ID

Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The following theorem is proved: For all $k$-connected graphs $G$ and $H$ each with at least $n$ vertices, the treewidth of the cartesian product of $G$ and $H$ is at least $k(n-2k+2)-1$. For $nggk$ this lower bound is asymptotically tight for particular graphs $G$ and $H$. This theorem generalises a well known result about the treewidth of planar grid graphs.

Recommendations

• Lower bounds for treewidth of product graphs
• Tree-width of product of a connected graph and a k-connected partial k-tree
• Polynomial treewidth forces a large grid-like-minor
• Connectivity of Cartesian products of graphs
• Bandwidth of the Cartesian product of two connected graphs

Cites work

• A note on graph minors and strong products
• A partial k-arboretum of graphs with bounded treewidth
• Bandwidth and pathwidth of three-dimensional grids
• Bandwidth of the Cartesian product of two connected graphs
• Clique minors in Cartesian products of graphs
• Graph minors. V. Excluding a planar graph
• Graph searching and a min-max theorem for tree-width
• On the bandwidth of 3-dimensional Hamming graphs
• On the bandwidth of a Hamming graph
• Optimal Indexing of the Vertices of Graphs
• Optimal labelling of a product of two paths
• Optimal numberings and isoperimetric problems on graphs
• The treewidth and pathwidth of hypercubes
• Treewidth and logical definability of graph products
• Treewidth lower bounds with brambles

Cited in

(10)

• Treewidth and logical definability of graph products
• Treewidth of the generalized Kneser graphs
• An improved planar graph product structure theorem
• Tree-width of product of a connected graph and a k-connected partial k-tree
• Treewidth of the \(q\)-Kneser graphs
• Treewidth of generalized Hamming graph, bipartite Kneser graph and generalized Petersen graph
• Grid minors and products
• Structural properties of graph products
• Lower bounds for treewidth of product graphs
• On the treewidth of toroidal grids

This page was built for publication: Treewidth of Cartesian products of highly connected graphs

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