Advances in Applied Mathematics
Vol.
13
No.
04
(
2024
), Article ID:
85701
,
5
pages
10.12677/aam.2024.134152
d棵树的笛卡尔乘积图的双宽度 研究
彭浩清
浙江师范大学数学科学学院,浙江 金华
收稿日期:2024年3月25日;录用日期:2024年4月22日;发布日期:2024年4月29日
![](http://html.hanspub.org/file/44-2623822x1_hanspub.png?20240430101230786)
摘要
在2020年Bonnet,Kim,Thomassé和Watrigant提出了双宽度。本文主要给出了对于任意正整数d,d棵树的笛卡尔积乘积图的双宽度的一个上界。
关键词
双宽度,笛卡尔乘积图,收缩序列
![](http://html.hanspub.org/file/44-2623822x2_hanspub.png?20240430101230786)
The Twin-Width Study of a Cartesian Product Graph of d Trees
Haoqing Peng
School of Mathematical Science, Zhejiang Normal University, Jinhua Zhejiang
Received: Mar. 25th, 2024; accepted: Apr. 22nd, 2024; published: Apr. 29th, 2024
![](http://html.hanspub.org/file/44-2623822x3_hanspub.png?20240430101230786)
ABSTRACT
In 2020, Bonnet, Kim, Thomassé, and Watrigant proposed twin-width. This article mainly gave that for any positive integer d, an upper bound on the twin-width of the Cartesian product graph of d trees.
Keywords:Twin-Width, Cartesian Product Graph, Contraction Sequences
![](http://html.hanspub.org/file/44-2623822x4_hanspub.png?20240430101230786)
Copyright © 2024 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
在本文中,我们只研究有限简单图,即所研究的简单图既不存在重边也不存在环。本文用 来表示图G的顶点集,用 来表示图G的边集。我们用符号Δ表示G中顶点的度数的最大值,并把它叫做图G的最大度。把与v相邻的所有顶点全体构成的集合称作v在图G的邻域,记作 。假设 是 的一个非空真子集,以 为顶点集,以两端点均在 中的边的全体为边集所组成的子图,称为G的由 所导出的子图,记为 ; 称为G的导出子图。我们把任意两个顶点间均有边连结的图称为完全图,记作Kn,其中n是图Kn的顶点数。
双宽度是由Bonnet,Kim,Thomassé和Watrigant [1] 于2020年引入的图和相关结构的相对较新的结构宽度度量,并给出了树的双宽度为2,路的双宽度为1,完全图的双宽度为0,还给出了d-维n-网格图的双宽度至多为3d。2021年,Bonnet,Geniet,Kim,Thomassé和Watrigant [2] 给出了任意图G和H的强积图的双宽度的上界为 。2022年,Pettersson和Sylvester给出了任意图G和H的笛卡尔积图的双宽度的上界为 ,还给出了d个完全图的笛卡尔乘积图的上界。对于任意正整数d,目前还没有人给出d个任意图的笛卡尔乘积图的上下界。本文朝着这个目标的前进,研究了d棵树的笛卡尔积图的双宽度的一个上界,希望能对后续学者研究d个任意图的笛卡尔乘积图的上下界提供一些参考价值。
接下来,本文将详细介绍双宽度的概念。一个三元组 ,其中E和R是V上两两不交的边集,E中的元素是黑边,R中的元素是红边。将导出子图的概念推广到三元组中。我们用 表示v的红色邻域。一个三元组 如果满足在 中最大度至多为d,则称这个三元组为d-三元组。任意图 可以被看成三元组 。给定一个三元组 和V的两个顶点u,v,三元组 可以通过在G上收缩u,v生成新点w得到,定义这个三元组的顶点集为 ,使得 ,并且使得 , ,其中 表示对称差。图G的一个d-收缩序列是一个以G开始,以单顶点三元组图结束的三元组序列,并使得所有中间三元组的最大红度至多为d。图G的双宽度是取遍G的所有d-收缩序列的最小值d,记为 。
图A和图B的笛卡尔积,记作 ,是一个以 为顶点集的图,如果对于不同的两个点 , 满足(1) 且 或者(2) 且 ,那么 和 相邻。
图A和图B的强积,记作 ,是一个以 为顶点集的图,如果对于不同的两个点 , 满足(1) 且 或者(2) 且 或者(3) 且 ,那么 和 相邻。
定理1.1 [1] 对于每个正整数d和n,d-维n-网格的双宽度至多为3d。
定理1.2 [2] 对任意图G和H,有 。
定理1.3 [3] 对任意图G和H,有 。
定理1.4 [3] 对于任意 , ,有 。
2. 主要定理
定理2.1对于任意最大度为Δ的树T,和任意正整数d,d棵树T的笛卡尔乘积图 ,记作 ,有 。
3. 主要定理证明
引理3.1 [2] 对于任意图H,令 为H的最大度,在图H上的每个三元组的双宽度至多 。
定理2.1 对于任意最大度为Δ的树T,和任意正整数d,d棵树T的笛卡尔乘积图 ,记作 ,有 。
证明:令 表示T的顶点数为n的树, 表示d棵树 的笛卡尔乘积图,其中 。我们将对d作归纳来证明 。
归纳基础:当 时, ,任意一个树 的双宽度至多为2。不妨假设 。
归纳假设: 存在一个 -收缩序列。
由于 为 与 的笛卡尔积,所以 可以被划分为n个集合 ,其中每个 ,使得每个 在 中的导出子图与 同构,其中 , ,使得在每个 收缩成一个顶点 后,得到的图为树 ,且 为树根也就是位于第一层, 位于树 的第二层,以此类推, 位于树 最后一层。由于 为 与 的笛卡尔积,因此对所有 , , , 如果 是 的父节点,则 与 之间有一条边相连。
根据归纳假设, 存在一个 -收缩序列。在每个 中并行的按照这个收缩序列进行收缩:在 上进行 的 -收缩序列的第一次收缩,然后在 上进行 的 -收缩序列的第一次收缩,直至在 上进行 的 -收缩序列的第一次收缩,接着在 上进行 的 -收缩序列的第二次收缩,然后在 上进行 的 -收缩序列的第二次收缩,直至在 上进行 的 -收缩序列的第二次收缩,以此类推,直至在 上进行 的 -收缩序列的最后一次收缩。通过这样做,可以维护以下不变量:
当在 中进行一次收缩时,即收缩 生成 ,其中 且 ,根据归纳假设, 在 中的红色邻点数至多为 ,由于 为 与 的笛卡尔积,所以 在 上的邻点的个数之和至多为Δ, 在 上的邻点的个数之和至多为Δ,所以在收缩 生成 后, 在 上的红色邻点的个数之和至多为2Δ,由于 为 与 的笛卡尔积,所以 中的任意顶点在除了 之外的其他所有顶点集上无邻点,所以 在除了 之外的其他所有顶点集上的红色邻点个数为0,因此 的红色邻点个数至多为 。
当在 中进行一次收缩时,其中 , ,即收缩 生成 ,其中 且 ,根据归纳假设根据归纳假设, 在 中的红色邻点数至多为 ,为了不失一般性,不妨假设 为 的父节点,则 在 上的红色邻点个数至多为1(这是因为 中相同的两个顶点在上一步已经被收缩成一个顶点了)。不妨假设, 的孩子节点为 ,由于 为 与 的笛卡尔积,所以 在 上的邻点个数总和至多为 , 在 上的邻点个数总和至多为 ,所以在 生成 后, 在 上的红色邻点个数总和至多为 。由于 为 与 的笛卡尔积,所以 中的任意顶点在除了 之外的其他所有顶点集上无邻点,所以 在除了 之外的其他所有顶点集上的红色邻点个数为0。因此 的红色邻点个数至多为 。
当在 中进行一次收缩时,即收缩 生成 ,其中 且 ,根据归纳假设, 在 中的红色邻点数至多为 ,为了不失一般性,不妨假设 为 的父节点, 在 上的红色邻点个数为1 (这是因为 中相同的两个顶点在上一步已经被收缩成一个顶点了)。由于 为 与 的笛卡尔积,所以 中的任意顶点在除了 之外的其他所有顶点集上无邻点,所以 在除了 之外的其他所有顶点集上的红色邻点个数为0。因此 的红色邻点个数至多为 。
而且每个不参与当前收缩的顶点在它自己所处的 中红色邻点个数至多为 (这是根据归纳假设得出的),其中 , 。若 为 的父节点,则根据 为 与 的笛卡尔积可知这个顶点在 上的红色邻点个数至多为1。为了不失一般性,不妨假设 的孩子节点为 ,由于树 的最大度为Δ,所以 的孩子节点个数至多为 ,根据 为 与 的笛卡尔积可知这个顶点在 上的红色邻点个数总和至多为 。由于 为 与 的笛卡尔积,所以 中的任意顶点在除了 之外的其他所有顶点集上无邻点,所以这个顶点在除了 之外的其他所有顶点集上的红色邻点个数为0。因此这个顶点的红色邻点个数至多为 。若 无父节点,即 为树 的根,也就是 且 所以 的孩子节点为 ,由于树 的最大度为Δ,所以 的孩子节点个数至多为Δ。根据 为 与 的笛卡尔积可知这个顶点在 上的红色邻点个数总和至多为2Δ。由于 为 与 的笛卡尔积,所以 中的任意顶点在除 之外的其他所有顶点集上无邻点,所以这个顶点在除了 之外的其他所有顶点集上的红色邻点个数为0。因此这个顶点的红色邻点个数至多为 。
当这个进程结束后,每个 都被收缩成一个顶点,因此得到的一个三元组是树T上的一个三元组,根据引理3.1可得这个三元组的双宽度至多为 。
因此我们得到了 存在一个 -收缩序列。也就是 。
4. 结语
在图论中,对双宽度的研究,很多学者做出了杰出的贡献,但对于不同的图类和乘积图上的双宽度研究还值得进一步探讨。本文给出了对于任意正整数d,d棵树的笛卡尔积图的双宽度的一个上界为 。若把树T扩展为任意图后的研究是值得进一步探讨的问题。
文章引用
彭浩清. d棵树的笛卡尔乘积图的双宽度研究
The Twin-Width Study of a Cartesian Product Graph of d Trees[J]. 应用数学进展, 2024, 13(04): 1618-1622. https://doi.org/10.12677/aam.2024.134152
参考文献
- 1. Bonnet, É., Kim, E.J., Thomassé, S. and Watrigant, R. (2020) Twin-Width I: Tractable FO Model Checking. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Durham, NC, 16-19 November 2020, 601-612. https://doi.org/10.1109/FOCS46700.2020.00062
- 2. Bonnet, É., Geniet, C., Kim, E.J., Thomassé, S. and Watrigant, R. (2021) Twin-Width II: Small Classes. In: Marx, D., Ed., Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1977-1996. https://doi.org/10.1137/1.9781611976465.118
- 3. Pettersson, W. and Sylvester, J. (2022) Bounds on the Twin-Width of Product Graph. arXiv:2202.11556,2022 https://doi.org/10.46298/dmtcs.10091