Geodesic
Bounds on the Twin-Width of Product Graphs
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1.

Voir la notice de l'article provenant de la source Episciences

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 $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\'{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.
DOI : 10.46298/dmtcs.10091
Classification : 05C12, 05C69, 05C76 
@article{DMTCS_2023_25_1_a16,
     author = {Pettersson, William and Sylvester, John},
     title = {Bounds on the {Twin-Width} of {Product} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2023-2024},
     doi = {10.46298/dmtcs.10091},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10091/}
}
TY  - JOUR
AU  - Pettersson, William
AU  - Sylvester, John
TI  - Bounds on the Twin-Width of Product Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10091/
DO  - 10.46298/dmtcs.10091
LA  - en
ID  - DMTCS_2023_25_1_a16
ER  - 
%0 Journal Article
%A Pettersson, William
%A Sylvester, John
%T Bounds on the Twin-Width of Product Graphs
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10091/
%R 10.46298/dmtcs.10091
%G en
%F DMTCS_2023_25_1_a16
Pettersson, William; Sylvester, John. Bounds on the Twin-Width of Product Graphs. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1. doi : 10.46298/dmtcs.10091. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10091/

Cité par Sources :