William Pettersson ; John Sylvester - Bounds on the Twin-Width of Product Graphs

dmtcs:10091 - Discrete Mathematics & Theoretical Computer Science, June 9, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.10091
Bounds on the Twin-Width of Product GraphsArticle

Authors: William Pettersson ; John Sylvester ORCID

    Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomassé & Watrigant. Given two graphs $G$ and $H$ and a graph product $\star$, we address the question: is the twin-width of $G\star H$ 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é & 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é & 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.

    Volume: vol. 25:1
    Section: Graph Theory
    Published on: June 9, 2023
    Accepted on: May 17, 2023
    Submitted on: September 28, 2022
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05C99, 68R10,G.2.2
      Source : OpenAIRE Graph
    • Multilayer Algorithmics to Leverage Graph Structure (MultilayerALGS); Funder: UK Research and Innovation; Code: EP/T004878/1

    Consultation statistics

    This page has been seen 509 times.
    This article's PDF has been downloaded 384 times.