关于图笛卡尔积和子式的注记

A Note on Graph Cartesian Products and Minors

摘要: 设$G\square H$ 和$G\cdot H$ 分别表示图$G$ 和$H$ 的笛卡尔积和字典积。本文研究了图积中的子式问题。特别地，我们通过构造方法证明，对任意简单图$G$ 和连通图$H$ ，图$G\cdot H$ 是图$G\square H^k$ 的一个子式，其中$H^k$ 是$H$ 的$k$ 重笛卡尔积且$k=\chi \left(G\right)$ 。这一结论推广了Wood的早期结果。此外，我们还改进了Wood中$\eta \left(G\square S_t\right)$ 的下界，其中$S_t=k_{1,t}$ 。

Abstract: Let $G\square H$ and $G\cdot H$ denote the Cartesian product and the lexicographic product of graphs $G$ and $H$ , respectively. In this note, we investigate the graph minor in products of graphs. In particular, we show that, for any simple graph $G$ and any connected graph $H$ , the graph $G\cdot H$ is a minor of the graph $G\square H^k$ , where $H^k$ is the k-fold Cartesian product of $H$ and $k=\chi \left(G\right)$ . This generalizes an earlier result of Wood. Moreover, we improve the lower bound of $\eta \left(G\square S_t\right)$ in Wood, where $S_t=k_{1,t}$ .

1. 引言

本文所考虑的图均为无向简单图。未定义的术语和记号参见文献[1]。

定义1.1 设$G,H$ 为图，$G*H$ 表示$G$ 和$H$ 的一种特定图乘积。$G*H$ 定义在顶点集上：

$V\left(G*H\right)=V\left(G\right)\times V\left(H\right).$

对于$V\left(G*H\right)$ 中的两个顶点$u=\left(u_1,u_2\right)$ 和$v=\left(v_1,v_2\right)$ ，它们在$G*H$ 中相邻当且仅当：

• 笛卡尔积$G\square H$ ：$u_1=v_1$ 且$u_2{v}_2\in E\left(H\right)$ ，或$u_2=v_2$ 且$u_1{v}_1\in E\left(G\right)$ ；

• 强积$G⊠H$ ：$u_1=v_1$ 且$u_2{v}_2\in E\left(H\right)$ ，或$u_2=v_2$ 且$u_1{v}_1\in E\left(G\right)$ ，或$u_1{v}_1\in E\left(G\right)$ 且$u_2{v}_2\in E\left(H\right)$ ；

• 字典积$G\cdot H$ ：$u_1{v}_1\in E\left(G\right)$ 或$u_1=v_1$ 且$u_2{v}_2\in E\left(H\right)$ 。

$G⊠H$ 是从$G$ 的一个副本出发，将$G$ 中的每个顶点替换为$H$ 的一个副本而得到的，并且当$u_1{v}_1\in E\left(G\right)$ 且$u_2{v}_2\in E\left(H\right)$ 时，$\left(u_1,u_2\right)\left(v_1,v_2\right)\in E\left(G⊠H\right)$ 。$G\cdot H$ 则是从$G$ 的一个副本出发，将$G$ 中的每个顶点替换为$H$ 的一个副本而得到的，对于$G$ 中的每条边$u_1{v}_1\in E\left(G\right)$ ，在对应的两个$H$ 副本之间添加所有可能的边，即对于任意$u_2,v_2\in V\left(H\right)$ ，连接$\left(u_1,u_2\right)$ 和$\left(v_1,v_2\right)$ 。

在图同构意义下，图笛卡尔积运算满足交换律与结合律。因此，对任意有限个图$G_1,G_2,\cdots ,G_k$ ，图$G_1\square G_2\square \cdots \square G_k$ 是良定义的。此时我们定义图$G:=G_1\square G_2\square \cdots \square G_k$ 的顶点集为

$V\left(G\right)=\left\{\left(v_1,v_2,\cdots ,v_k\right):v_i\in V\left(G_i\right),i\in \left[k\right]\right\}.$

对于两个不同的顶点$u=\left(u_1,\cdots ,u_k\right)$ 与$v=\left(v_1,\cdots ,v_k\right)$ ，我们有$uv\in E\left(G\right)$ 当且仅当存在唯一的指$i\in \left[k\right]$ ，使得

$u_i{v}_i\in E\left(G_i\right)且u_j=v_j对所有j\ne i成立.$

在此情形下，称边$uv$ 位于第$i$ 维。对于任意图$G$ 及整数$k\ge 1$ ，记

$G^k:=\underset{k}{\underbrace{G\square G\square \cdots \square G}}$

为$G$ 的$k$ 重笛卡尔积图。

定义1.2 设$H$ 是一个顶点集为$\left\{1,2,\cdots ,n\right\}$ 的图。若存在$G$ 的$n$ 个两两不交的非空顶点子集$X_1,X_2,\cdots ,X_n\subseteq V\left(G\right)$ ，满足：

(1) 对每个$i\in \left[n\right]$ ，$G\left[X_i\right]$ 是连通的；

(2) 对任意边$ij\in E\left(H\right)$ ，图$G$ 中存在一条边连接$X_i$ 与$X_j$ ，即存在$u\in X_i$ 与$v\in X_j$ 使得$uv\in E\left(G\right)$ ；

则称$H$ 是$G$ 的一个子式，记为$H\preccurlyeq G$ 。当$H=K_t$ 为完全图时，称$H$ 为$G$ 的一个团子式。此时，上述定义等价于：$G$ 中存在$t$ 个两两不交的连通子图，且任意两个子图之间均存在至少一条边相连。

给定图$G$ ，称$G$ 中最大团子式所对应的完全图的顶点数，即满足$K_t\preccurlyeq G$ 的最大整数$t$ 为图$G$ 的Hadwiger数，记作$\eta \left(G\right)$ 。Hadwiger数是图结构复杂性的主要度量之一。图乘积结构研究为描述复杂图类提供了基于简单构建块的强大框架[2]-[4]。Kotlov [5]开创了对图积中子式的研究，并证明，对任意二分图$G$ ，强积$G⊠K_2$ 是$G\square C_4$ 的一个子式。该结果的推论给出了$\eta \left(K_2^k\right)$ 最好的下界。Chandran和Sivadasan [6]研究了笛卡尔积图中的团子式。随后，Wood [7]以及Chandran、Kostochka和Raju [8]继续研究了笛卡尔积图中的团子式。特别地，Wood [7]证明了以下结果：

定理1.3 [7] 设$H$ 为一个连通图，$G$ 为一个二分图，则$G\cdot H\preccurlyeq G\square H\square H$ 。

给定图$G$ ，若存在一个映射$f:V\to \left\{1,2,\cdots ,k\right\}$ 使得对任意边$uv\in E$ 有$f\left(u\right)\ne f\left(v\right)$ ，则称$G$ 是$k$ -可着色的。色数$\chi \left(G\right)$ 是满足该条件的最小正整数$k$ 。在本文中，我们延续了关于笛卡尔积图中字典积子式的研究，将Wood [7]的结果推广到了更一般的情况：

定理1.4 设$H$ 为一个连通图，$G$ 为一个$\chi \left(G\right)=k$ 的图，则$G\cdot H\preccurlyeq G\square H^k$ 。

Wu、Yang和Yu [9]证明了，对任意连通图$G$ ，强积$G⊠K_n$ 是$G\square K_n^{\chi (G)}$ 的一个子式。由强积和字典积的定义易知$G\cdot K_n$ 和$G⊠K_n$ 同构，故该结果也可以写成：对任意连通图$G$ ，$G\cdot K_n$ 是$G\square K_n^{\chi (G)}$ 的一个子式。因此，定理1.4也是Wu、Yang和Yu [9]结果的推广。

此外，我们还改进了Wood [7]中$\eta \left(G\square S_t\right)$ 的下界，且改进后的下界是紧的：

命题1.5 对任意$n$ 个顶点的连通图$G$ 和任意整数$t\ge 1$ ，有

$\eta \left(G\square S_t\right)\ge \min \left\{\left|V\left(G\right)\right|,t+\omega \left(G\right)\right\}.$

2. 预备知识

设$G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个连通图。设$S$ 是$V\left(G\right)$ 的一个非空子集。以$S$ 为顶点集，以$G$ 中两个端点均在$S$ 中的所有边为边集所组成的子图称为$G$ 的由$S$ 导出的子图，记为$G\left[S\right]$ ，这时，也称$G\left[S\right]$ 为$G$ 的导出子图。称$G$ 中最大团所含的顶点数为图$G$ 的团数，记作$\omega \left(G\right)$ 。叶子是指度为1的顶点，记$S_t$ 为具有$t$ 个叶子的星图，即$S_t=K_{1,t}$ 。对任意整数$m,n\in \mathbb{Z}$ 且$m<n$ ，定义$\left[m,n\right]:=\left\{m,m+1,\cdots ,n\right\}$ ，并记$\left[n\right]:=\left[1,n\right]$ 。

若$P=\left\{V_1,V_2,\cdots ,V_k\right\}$ 是图$G$ 的非空顶点子集的一个集合，且满足$G$ 的每个顶点恰好属于$P$ 中的一个元素，即$V_i\ne \varnothing$ ，${\displaystyle \underset{i=1}{\overset{k}{\cup }}{V}_i}=V\left(G\right)$ ，且对任意$i\ne j$ 有$V_i\cap V_j=\varnothing$ ，则称$P$ 是图$G$ 的一个划分，$P$ 中的每个元素称为一个部。若$P$ 和$P\text{'}$ 是图$G$ 的两个不同的划分，且$P$ 的每个部都与$P\text{'}$ 的每个部有非空交，则称$P$ 和$P\text{'}$ 是交叉的。划分$P$ 的商图(关于$G$ )记为$G/P$ ，其顶点集为$P$ 中的非空部，其中两个不同的部$A,B\in P$ 在$G/P$ 中相邻，当且仅当存在$u\in A$ 与$v\in B$ ，使得$u$ 与$v$ 在$G$ 中相邻。

3. 证明

引理3.1 对每个连通图$H$ 及任意整数$k\ge 1$ ，均存在$H^k$ 的$k$ 个两两交叉的划分，使得

(a) 每个划分的每个部都在$H^k$ 中导出一个连通子图；

(b) 对每个划分$P$ ，商图$H^k/P$ 均同构于$H$ 。

证明 设$V\left(H\right)=\left\{1,2,\cdots ,n\right\}$ 。对任意$i\in \left[k\right]$ 和$j\in \left[n\right]$ ，定义

$A_{i,j}=\left\{\left(l_1,\cdots ,l_{i-1},j,l_{i+1},\cdots ,l_k\right):l_{i^{\prime }}\in \left[n\right],i^{\prime }\ne i\right\}.$

则对每个$i\in \left[k\right]$ ，集合$\left\{A_{i,1},A_{i,2},\cdots ,A_{i,n}\right\}$ 构成$H^k$ 的一个划分，从而得到$k$ 个划分。

我们首先证明这$k$ 个划分两两交叉。任取来自两个不同划分的两个部，不妨设为$A_{i_1,x}$ 和$A_{i_2,y}$ ，其中$i_1\ne i_2$ 且$x,y\in \left[n\right]$ 。取顶点

$\left(l_1,\cdots ,l_k\right),其中l_{i_1}=x,l_{i_2}=y,其余l_r=1$

则该顶点同时属于$A_{i_1,x}$ 与$A_{i_2,y}$ ，因此任意两个不同划分是交叉的。

接下来证明(a)。注意到$H^k\left[A_{i,j}\right]$ 同构于$H^{k-1}$ ，而$H$ 连通蕴含$H^{k-1}$ 连通，故每个部在$H^k$ 中诱导的子图是连通的。

下面证明(b)。任取一个划分$P$ ，不妨设$P=\left\{A_{i,1},A_{i,2},\cdots ,A_{i,n}\right\}$ 。显然$\left|V\left(H^k/P\right)\right|=n=\left|V\left(H\right)\right|$ 。

首先证明：若$j_s{j}_t\in E\left(H\right)$ ，则$A_{i,j_s}$ 与$A_{i,j_t}$ 在$H^k/P$ 中相邻。取任意

$\left(l_1,\cdots ,l_{i-1},j_s,l_{i+1},\cdots ,l_k\right)\in A_{i,j_s}$

和

$\left(l_1,\cdots ,l_{i-1},j_t,l_{i+1},\cdots ,l_k\right)\in A_{i,j_t}$

由于仅在第$i$ 个坐标处不同，且$j_s{j}_t\in E\left(H\right)$ ，根据$k$ 重笛卡尔积图的定义，上述两个顶点在$H^k$ 中相邻，从而对应的两个部在商图中相邻。

反之，设$A_{i,j_s}$ 与$A_{i,j_t}$ 在$H^k/P$ 中相邻，其中$j_s\ne j_t$ 。则存在

$u=\left(l_1,\cdots ,l_{i-1},j_s,l_{i+1},\cdots ,l_k\right)\in A_{i,j_s}$

和

$v=\left({l^{\prime }}_1,\cdots ,{l^{\prime }}_{i-1},j_t,{l^{\prime }}_{i+1},\cdots ,{l^{\prime }}_k\right)\in A_{i,j_t},$

使得$u$ 与$v$ 在$H^k$ 中相邻。由于$u$ 与$v$ 在$H^k$ 中相邻，根据笛卡尔积的定义，存在唯一的指标$r\in \left[k\right]$ ，使得$l_r{l^{\prime }}_r\in E\left(H\right)$ ，且对所有$l\ne r$ 有$l_l={l^{\prime }}_l$ 。又由于$j_s\ne j_t$ ，可知$u$ 与$v$ 在第$i$ 个坐标上不同，从而必有$r=i$ ，并且$j_s{j}_t\in E\left(H\right)$ 。

因此，$H^k/P$ 与$H$ 的边集一一对应，从而$H^k/P\cong H$ 。

≤

定理1.4 设$H$ 为一个连通图，$G$ 为一个满足$\chi \left(G\right)=k$ 的图，则$G\cdot H\preccurlyeq G\square H^k$ 。

证明 由于$G$ 是k-可着色的，存在一个正常的k-着色

$c:V\left(G\right)\to \left[k\right],$

使得对任意$i\in \left[k\right]$ ，集合$\left\{v\in V\left(G\right):c\left(v\right)=i\right\}$ 在$G$ 中诱导一个独立集。

设$V\left(H\right)=\left\{1,2,\cdots ,n\right\}$ 。由引理3.1，图$H^k$ 存在$k$ 个两两交叉的划分，并且满足条件(a)与(b)。记这些划分为

$\left\{A_{i,1},A_{i,2},\cdots ,A_{i,n}\right\},i\in \left[k\right].$

对$G\cdot H$ 的每个顶点$\left(v,j\right)$ ，定义$G\square H^k$ 中的顶点子集

$X_{v,j}=\left\{\left(v,u\right):u\in A_{c(v),j}\right\}.$

由于对每个$i\in \left[k\right]$ ，$\left\{A_{i,1},\cdots ,A_{i,n}\right\}$ 是$H^k$ 的一个划分，可知

$\left\{X_{v,j}:v\in V\left(G\right),j\in \left[n\right]\right\}$

构成了$G\square H^k$ 顶点集的一个划分。

下面验证子式关系。由引理3.1(a)，每个$A_{c(v),j}$ 在$H^k$ 中诱导的子图是连通的，从而根据笛卡尔积的定义，每个$X_{v,j}$ 在$G\square H^k$ 中诱导的子图亦是连通的。

设$\left(v,j_1\right)$ 与$\left(v^{\prime },j_2\right)$ 是$G\cdot H$ 中的两个相邻顶点，我们证明其对应的点集$X_{v,j_1}$ 与$X_{v^{\prime },j_2}$ 在$G\square H^k$ 中相邻。根据字典积的定义，要么$v{v}^{\prime }\in E\left(G\right)$ ，要么$v=v^{\prime }$ 且$j_1{j}_2\in E\left(H\right)$ 。

情形1 $v{v}^{\prime }\in E\left(G\right)$ 。

由于$c$ 是一个正常着色，必有$c\left(v\right)\ne c\left(v^{\prime }\right)$ 。因此，划分$\left\{A_{c(v),1},\cdots ,A_{c(v),n}\right\}$ 与$\left\{A_{c(v^{\prime }),1},\cdots ,A_{c(v^{\prime }),n}\right\}$ 是交叉的，从而存在顶点

$u\in A_{c(v),j_1}\cap A_{c(v^{\prime }),j_2}.$

于是$\left(v,u\right)\in X_{v,j_1}$ 与$\left(v^{\prime },u\right)\in X_{v^{\prime },j_2}$ 在$G\square H^k$ 中相邻。

情形2 $v=v^{\prime }$ 且$j_1{j}_2\in E\left(H\right)$ 。

此时，任取

$u=\left(l_1,\cdots ,l_{c(v)-1},j_1,l_{c(v)+1},\cdots ,l_k\right)\in A_{c(v),j_1}$

和

$u^{\prime }=\left(l_1,\cdots ,l_{c(v)-1},j_2,l_{c(v)+1},\cdots ,l_k\right)\in A_{c(v),j_2},$

由于$u$ 与$u\text{'}$ 仅在第$c\left(v\right)$ 个坐标处不同，且$j_1{j}_2\in E\left(H\right)$ ，可知$\left(v,u\right)\in X_{v,j_1}$ 与$\left(v,u^{\prime }\right)\in X_{v,j_2}$ 在$G\square H^k$ 中相邻。

综上，在两种情形下，$G\cdot H$ 中的相邻顶点对应于$G\square H^k$ 中相邻的连通子图，因此由子式的定义可得$G\cdot H\preccurlyeq G\square H^k$ 。

≤

下面的结果在Wood [7]的下界基础上作了改进。具体而言，我们将$G\square S_t$ 的Hadwiger数下界从$\min \left\{\left|V\left(G\right)\right|,t+1\right\}$ 提升到$\min \left\{\left|V\left(G\right)\right|,t+\omega \left(G\right)\right\}$ 。

命题1.5 对任意$n$ 个顶点的连通图$G$ 和任意整数$t\ge 1$ ，有

$\eta \left(G\square S_t\right)\ge \min \left\{\left|V\left(G\right)\right|,t+\omega \left(G\right)\right\}.$

证明 设$H$ 是$G$ 的一个最大团，记$\omega \left(G\right)=c$ ，并令$V\left(H\right)=\left\{v_{n-c+1},\cdots ,v_n\right\}$ 。相应地，设$V\left(G\right)\backslash V\left(H\right)=\left\{v_1,\cdots ,v_{n-c}\right\},V\left(S_t\right)=\left\{r\right\}\cup \left[t\right]$ 。令$k=\min \left\{n,t+c\right\}$ 。下面构造$G\square S_t$ 的$k$ 个两两互不相交的顶点子集。

首先，对每个$i\in \left[n-c+1,n\right]$ ，定义

$X_i=\left\{\left(v_i,r\right)\right\}$ ,

这些点集两两不交。且由于$H$ 是团，对任意不同的$i,j\in \left[n-c+1,n\right]$ ，顶点$\left(v_i,r\right)$ 与$\left(v_j,r\right)$ 在$G\square S_t$ 中相邻。

接下来，对每个$a\in \left[k-c\right]\subseteq \left[t\right]$ (由于$k=\min \left\{n,t+c\right\}$ ，所以$k-c\le t$ )，定义

$X_a=\left\{\left(v_a,r\right)\right\}\cup \left\{\left(v_j,a\right):j\in \left[n\right]\right\}.$

我们断言$X_a$ 在$G\square S_t$ 中诱导一个连通子图。事实上，由于$G$ 是连通图，又因为$\left(v_a,a\right)$ 与$\left(v_a,r\right)$ 在$G\square S_t$ 中相邻，可知$X_a$ 所诱导的子图是连通的。

对于不同的$a,b\in \left[k-c\right]$ ，点集$X_a$ 与$X_b$ 不相交，且顶点$\left(v_b,a\right)\in X_a$ 与$\left(v_b,r\right)\in X_b$ 相邻，因此$X_a$ 与$X_b$ 之间存在边相连。此外，对任意$a\in \left[k-c\right]$ 和$i\in \left[n-c+1,n\right]$ ，点集$X_a$ 与$X_i$ 不相交，且顶点$\left(v_i,r\right)\in X_i$ 与$\left(v_i,a\right)\in X_a$ 相邻。

综上所述，集合$\left\{X_1,\cdots ,X_{k-c}\right\}\cup \left\{X_{n-c+1},\cdots ,X_n\right\}$ 给出了$G\square S_t$ 中的$k$ 个两两不交的顶点集，其诱导子图均连通，且任意两个诱导子图之间均存在边相连。因此$K_k\preccurlyeq G\square S_t$ ，从而

≤

当$G$ 为一个至少含$t+2$ 个顶点的树图时，有$\omega \left(G\right)=2$ ，从而由上述命题可得

另一方面，由于$S_t$ 是$K_{t+1}$ 的子图，有$\eta \left(G\square S_t\right)\le \eta \left(G\square K_{t+1}\right)$ 。而Wood在[7]的定理10.1中证明了$\eta \left(G\square K_{t+1}\right)=t+2$ ，因此$\eta \left(G\square S_t\right)\le t+2$ 。综上可知$\eta \left(G\square S_t\right)=t+2$ ，从而命题1.5中给出的下界在该情形下是紧的。

命题1.5在Wood [7]的结果基础上给出了实质性的改进，将常数1提升为$\omega \left(G\right)$ 能够有效刻画$G$ 中团结构对笛卡尔积图Hadwiger数的贡献。为说明这一点，取$G=K_n$ ，其中$n\ge 2$ 。此时$\omega \left(G\right)=n$ 且$\left|V\left(G\right)\right|=n$ 。由Wood的下界只能得到$\eta \left(K_n\square S_t\right)\ge t+1$ ，该下界与$n$ 无关。而由命题1.5可得。当$n\gg t$ 时，新下界相较于$t+1$ 有显著提升。