Bounds on the Twin-Width of Product Graphs

DOI10.46298/DMTCS.10091MaRDI QIDQ6131799zbMATH OpenOpenAlexFDO

Authors

Publication date 18 April 2024

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph productsHamming graphstwin-width

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomass'{e} & Watrigant. Given two graphs $G$ and $H$ and a graph product $star$, we address the question: is the twin-width of $GstarH$ bounded by a function of the twin-widths of $G$ and $H$ and their maximum degrees? It is known that a bound of this type holds for strong products (Bonnet, Geniet, Kim, Thomass'{e} & Watrigant; SODA 2021). We show that bounds of the same form hold for Cartesian, tensor/direct, corona, rooted, replacement, and zig-zag products. For the lexicographical product it is known that the twin-width of the product of two graphs is exactly the maximum of the twin-widths of the individual graphs (Bonnet, Kim, Reinald, Thomass'{e} & Watrigant; IPEC 2021). In contrast, for the modular product we show that no bound can hold. In addition, we provide examples showing many of our bounds are tight, and give improved bounds for certain classes of graphs.

Recommendations

• Bounds for the twin-width of graphs
• Twin-width of graphs with tree-structured decompositions
• Twin-width can be exponential in treewidth

Cites work

• scientific article; zbMATH DE number 1054727 (Why is no real title available?)
• scientific article; zbMATH DE number 6813611 (Why is no real title available?)
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• scientific article; zbMATH DE number 3385666 (Why is no real title available?)
• scientific article; zbMATH DE number 7803584 (Why is no real title available?)
• A new graph product and its spectrum
• A note on the derivation of maximal common subgraphs of two directed or undirected graphs
• An Elementary Construction of Constant-Degree Expanders
• An improved inequality related to Vizing's conjecture
• An inequality related to Vizing's conjecture
• Applications of product colouring
• Bounds for the twin-width of graphs
• Compact representation for matrices of bounded twin-width
• Counterexamples to Hedetniemi's conjecture
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Fourier analysis and large independent sets in powers of complete graphs
• Graph products, Fourier analysis and spectral techniques
• Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded
• Graphs with Given Group and Given Graph-Theoretical Properties
• Handbook of product graphs
• On a Vizing-like conjecture for direct product graphs
• On the corona of two graphs
• Products of graceful trees
• RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs
• Subgraph isomorphism, matching relational structures and maximal cliques
• The Spectrum of the Corona of Two Graphs
• The \(k\)-path vertex cover of rooted product graphs
• The behavior of clique-width under graph operations and graph transformations
• The chromatic number and other functions of the lexicographic product
• The independence polynomial of rooted products of graphs
• The modular product and existential closure
• Twin-width IV: ordered graphs and matrices
• Twin-width and generalized coloring numbers
• Twin-width and polynomial kernels
• Twin-width. I: Tractable FO model checking
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• \(L(2,1)\)-labelings on the modular product of two graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey

Cited in

(2)

• Twin-width of graphs with tree-structured decompositions
• Neighbourhood complexity of graphs of bounded twin-width

This page was built for publication: Bounds on the Twin-Width of Product Graphs

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