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

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}$ .