论文标题
产品图的双宽度上的界限
Bounds on the Twin-Width of Product Graphs
论文作者
论文摘要
双宽度是Bonnet，Kim，Thomassé＆Watrigant最近引入的图形宽度参数。给定两个图表$ g $和$ h $和一个图产品$ \ star $，我们解决了一个问题：$ g \ star h $的双宽度是由$ g $和$ h $的双宽度的函数界定的吗？众所周知，这种类型的界限适用于强产物（Bonnet，Geniet，Kim，Thomassé＆Watrigant； Soda 2021）。我们表明，笛卡尔，张量/直接，电晕，根，替换和锯齿形产品的相同形式的界限。对于词典产物，众所周知，两个图的产物的双宽度正是单个图的双宽度的最大值（Bonnet，Kim，Reinald，Thomassé和Watrigant; Ipec 2021）。相比之下，对于模块化产品，我们表明没有包裹可以容纳。此外，我们提供的例子表明我们的许多界限都很紧，并为某些类别的图形提供了改进的界限。
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.
