Bounds on the Twin-Width of Product Graphs

DOI10.46298/DMTCS.10091arXiv2202.11556OpenAlexW4379093231MaRDI QIDQ6131799FDOQ6131799

Author name not available (Why is that?)

Publication date: 18 April 2024

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

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.

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)

Cites Work

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