4-连通P₀-Minor-Free图的特征

A Characterization of 4-Connected Graphs with No P₀-Minor

摘要: 设H和G是两个图，如果图H可以通过从图G的一个子图中收缩边然后删除产生的环和平行边得到，我们就把图H叫做图G的一个minor。如果图G没有同构于图H的minor，我们称图G为H-minor-free图。图论中很多猜想都与H-minor-free图有关，例如Hadwiger猜想和Tutte 4-流猜想等。为了推动这些猜想的解决，我们目前非常关注Petersen-minor-free图的结构。由于它们都是15条边的3-连通图，直接刻画起来比较困难。因此为了刻画Petersen-minor-free图，许多学者尝试对每个边数小于15的3-连通图进行刻画去接近Petersen-minor-free图。记P₀为Petersen收缩两条完美匹配边和一条非完美匹配边得到的子图基础上添加一条边得到的13条边的图。本文下面将给出完整的4-连通P₀-minor-free图的刻画。

Abstract: For two given graphs H and G, if H can be obtained from a subgraph of G by contracting edges then deleting the resulting loops and parallel edges, we call H a minor of G. If G has no minor isomorphic to H, G is H-minor-free, and H is a forbidden minor of G. In graph theory, many important conjectures are related to H-minor-free graphs such as Hadwiger’s conjecture and Tutte’s 4-flow conjecture. To solve the above conjectures, we attempt to characterize Petersen-minor-free graphs. Let H is a graph with 15 edges. It is difficult to characterize H-minor-free graphs, thus to characterize Petersen-minor-free graphs, many scholars try to characterize every 3-connected graph with edges less than 15 to get close to Petersen graph. We denote the graph obtained by contracting two edges of a perfect matching of the Petersen, contracting one other edge and adding one edge. In this paper, we characterize 4-connected P₀-minor-free graphs.

1. 引言

图的刻画一直是图论研究过程中的一个重要课题。图的生成定理又叫做图的链式定理。链式定理对于研究具有某一类特征的图有着极为重要的作用。Tutte的轮子定理被称为3-连通图的生成定理。通过这个定理，我们可以得到所有的3-连通图。Martinov给出了4-连通图的链式定理，后面Qin和Ding对这个链式定理进行了进一步的加强。

在图的刻画中，刻画一个图的minor-free图一直是一个非常有趣的话题。一个图的minor-free图的刻画可以给出一个图非常具体的特征。例如一个图是平面图当且仅当它不包含 $K_5$ 和 $K_{3，3}$ 作为minor。图论中很多猜想都与H-minor-free图有关，例如Hadwiger猜想和Tutte 4-流猜想等。为了推动这些猜想的解决，我们目前非常关注Petersen-minor-free图的结构。由于它们都是15条边的3-连通图，直接刻画非常困难，因此许多学者尝试对每个边数小于15的3-连通图进行刻画去接近Petersen-minor-free图。其中，A.B.Ferguson对通过收缩Petersen中三条完美匹配边得到的图作为禁止minor的图进行了完整地刻画。对于边数少于11的3-连通图H，Ding刻画了所有的H-minor-free图 [1] 。对于12条边的3-连通图， $V_8$ -minor-free图，cube-minor-free图以及Oct-minor-free图已经得到完整的刻画 [2] [3] 。13条边的3-连通图一共有51个。，其中内部四连通图只有3个，其中Oct+e是其中一个并且4-连通Oct+e-minor-free图得到了完整地刻画 [4] 。另外Oct对一个顶点3-分离可以得到2个图，Jia对这两类图的4-连通minor-free图给出了部分刻画 [5] 。除此之外，刻画一个图的minor-free图离不开链式定理，并且还有很多与minor-free图的刻画以及性质的研究，可见文献 [6] - [14] 。我们记P₀为Petersen收缩两条完美匹配边和一条非完美匹配边得到的子图基础上添加一条边得到的13条边的3-连通图。本文将完整地刻画所有的4-连通P₀-minor-free图，给出一个4-连通图是P₀-minor-free图的充要条件。

2. 预备知识

简单图是没有自环和重边的图，本文中我们考虑的都是简单图。G为一个图，我们用 $V\left(G\right)$ 来表示图G的顶点集， $\left|V\left(G\right)\right|$ 表示图G的顶点数，用 $E\left(G\right)$ 表示图G的边集， $\left|E\left(G\right)\right|$ 表示图G的顶点数。

令e为图G的一条边，我们用 $G/e$ 表示由图G收缩一条边得到的图，用 $G\backslash e$ 表示由图G删除一条边得到的图，给定两个图 $G_1$ 和 $G_2$ ，如果 $G_1$ 同构于 $G_2$ ，记为 $G_1\cong G_2$ 。设G和H是两个图，如果图H可以通过从图G的一个子图中收缩边然后删除产生的环和平行边得到，我们就把图H叫做图G的一个minor，用 $H{\le }_{m}G$ 来表示。如果图G没有同构于图H的minor，我们称图G为H-minor-free图。

如果一个圈C的长度为n ( $n\ge 3$ )，我们记这个圈为 $C_n$ 。圈 $C_n$ ( $n\ge 5$ )的平方，记作 $C_n^2$ ，是通过圈 $C_n=v_0{v}_1\cdots v_n$ 加上n条边 $v_i{v}_{i+2}$ ( $0\le i\le n-1$ )得到的，我们令 ${\varsigma }_0=\left\{C_{2n}^2:n\ge 3\right\}$ ， ${\varsigma }_1=\left\{C_{2n+1}^2:n\ge 2\right\}$ 。记 $D{W}_n$ 为通过两个相邻点分别与圈 $C_n$ 上个每个点连边得到的图，令 $DW=\left\{D{W}_n:n\ge 3\right\}$ 。

令 $v$ 为4-连通图 $G$ 的一个顶点。4-分离顶点 $v$ 就是按如下操作产生一个新图 $G^{\prime }$ 。给定两个集合 $A,B\subseteq N_G\left(v\right)$ ， $\min \left\{\left|A\right|,\left|B\right|\right\}\ge 3$ 。从图中移除顶点 $v$ ，然后添加两个新的顶点 $v^{\prime },v^{″}$ 使得在新图 $G^{\prime }$ 之中 $N\left(v^{\prime }\right)=A\cup \left\{v^{″}\right\}$ ， $N\left(v^{″}\right)=B\cup \left\{v^{\prime }\right\}$ 。不难看出，图 $G^{\prime }$ 也是4-连通图。

Martinov给出了4-连通图的链式定理，证明了任意4-连通图都可以由 ${\varsigma }_0\cup {\varsigma }_1\cup L$ 中的4-连通图都可以由 $C_6^2$ 或者 $C_5^2$ 反复地进行4-分离点得到。

定理2.1 [15] 一个4-连通图是 $\overline{P_7}$ -minor-free的当且仅当它是平面图或者属于 $DW\cup {\varsigma }_1\cup {\rm K}\cup \left\{K_6,L\left(K_{3,3}\right),{\Gamma }_1,{\Gamma }_2,{\Gamma }_3,{\Gamma }_4,{\Gamma }_5\right\}$ (图1、图2)。

Figure 1. ${\Gamma }_1,{\Gamma }_2,{\Gamma }_3,{\Gamma }_4,{\Gamma }_5$

图1. ${\Gamma }_1,{\Gamma }_2,{\Gamma }_3,{\Gamma }_4,{\Gamma }_5$

Figure 2. K

图2. K

3. 4-连通P₀-Minor-Free图

本节将给出4-连通P₀-minor-free图的完整刻画。

引理3.1 若图G是 ${\varsigma }_1$ 中的4-连通图，则图G是P₀-minor-free图当且仅当图G是 $C_5^2$ 或者 $C_7^2$ 。

证明： $C_5^2$ 顶点数是5并且少于图P₀的顶点数，所以 $C_5^2$ 是P₀-minor-free图。假设 $C_7^2$ 包含P₀作为minor，则P₀可以由 $C_7^2$ 删除或者收缩边得到。图P₀中点的最大度为5， $C_7^2$ 中点的最大度为4，所以 $C_7^2$ 是P₀-minor-free图。不难发现 $C_9^2$ 包含P₀作为minor (见图3)，所以若图G是 ${\varsigma }_1$ 中的4-连通图，则图G是P₀-minor-free图当且仅当图G是 $C_5^2$ 或者 $C_7^2$ 。引理3.1得证。

引理3.2 若图G是K中的4连通图，则则图G是P₀-minor-free图当且仅当图G属于集合 $\left\{K_5,D{W}_4,K_6\backslash e,K_{4,3}^4,K_{4,3}^{11}\right\}$ 。

证明： $K_5,D{W}_4,K_6\backslash e$ 的顶点数小于P₁的顶点数，所以 $K_5,D{W}_4,K_6\backslash e$ 都是P₁-minor-free图。假设 $K_{4，3}^4$ 包含P₀作为minor，则P₀可以由 $K_{4，3}^4$ 删除边得到。我们注意到P₀中顶点1，3，6为三个互不相邻点，顶点3，7，6，2的导出子图为一条4路。但是 $K_{4，3}^4$ 中除去3个互不相邻点以外的4个点构成不了一条4路，

Figure 3. P₀ minor in $C_7^2$

图3. $C_7^2$ 中的P₀ minor

所以 $K_{4，3}^4$ 是P₀-minor-free图(见图4)。类似地，假设 $K_{4，3}^{11}$ 包含P₀作为minor，则P₀可以由 $K_{4，3}^{11}$ 删除边以及收缩边得到。由于对称性，只考虑收缩 $K_{4，3}^{11}$ 中的一条边就可以。因为收缩一条边后所得的图中除去3个互不相邻的点以外的4个点不能构成一条4路， $K_{4，3}^{11}$ 是P₀-minor-free图(见图5)。我们注意到， $K_{4，3}^4$ 和 $K_{4，3}^6$ 都包含P₀作为minor (见图6)。对于 $i=1,2,5$ ， $K_{4，3}^i$ 包含 $K_{4，3}^3$ 作为minor，所以它们也都包含P₀作为minor。对于 $j=1,2,3,\cdots ,10$ ， $K_{4,4}^j$ 包含 $K_{4，3}^6$ 作为minor，因此它们都包含P₀作为minor。所以，引理3.2得证。

Figure 4. $K_{4,3}^4$ is P₀-minor-free

图4. $K_{4,3}^4$ 是P₀-minor-free图

Figure 5. $K_{4,4}^{11}$ is P₀-minor-free

图5. $K_{4,4}^{11}$ 是P₀-minor-free图

Figure 6. P₀ minor in $K_{4,3}^6$ and $K_{4,3}^3$

图6. $K_{4,3}^6,K_{4,3}^3$ 中的P₀ minor

引理3.3 若图G是一个4-连通图且属于集合 $DW\cup \left\{L\left(K_{3,3}\right),{\Gamma }_1,{\Gamma }_2,{\Gamma }_3,{\Gamma }_4,{\Gamma }_5\right\}$ ，则图G包含P₀作为minor。

证明： $D{W}_5$ 包含P₀作为minor (见图)，并且对于 $D{W}_n\left(n\ge 5\right)$ 包含 $D{W}_5$ 作为minor，所以集合 $DW$ 中的图都包含P₀作为minor。 ${\Gamma }_1$ 包含P₀作为minor， ${\Gamma }_2,{\Gamma }_3,{\Gamma }_4,{\Gamma }_5$ 包含 ${\Gamma }_1$ 作为minor，因此都包含有P₀作为minor (见图7)。不难看出， $L\left(K_{3,3}\right)$ 包含P₀作为minor (见图8)。所以，引理3.3得证。

Figure 7. P₀ minor in $D{W}_5$ and ${\Gamma }_1$

图7. $D{W}_5,{\Gamma }_1$ 中的P₀ minor

Figure 8. P₀ minor in $L\left(K_{3,3}\right)$

图8. $L\left(K_{3,3}\right)$ 中的P₀ minor

定理3.4 一个4-连通图G是P₀-minor-free图当且仅当它是平面图或属于 $\left\{K_6,K_6\backslash e,D{W}_4,C_5^2,C_7^2,K_{4,3}^4,K_{4,4}^{11}\right\}$ 。

证明：平面图的minor一定是平面图，所以所有的平面图都是P₀-minor-free图。我们注意到P₀是 $\overline{P_7}$ 的子图，根据定理2.1，以及引理3.1、3.2以及3.3的结果可得一个4-连通图G是P₀-minor-free图当且仅当它是平面图或属于 $\left\{K_6,K_6\backslash e,D{W}_4,C_5^2,C_7^2,K_{4,3}^4,K_{4,4}^{11}\right\}$ 。定理3.3得证。

4. 结论与展望

Petersen-minor-free图的刻画是一个重要的问题，但是Petersen图有15条边，直接刻画起来非常困难，于是许多学者通过刻画Pertersen子式作为禁止minor的图去接近Petersen-minor-free图。其中，A. B. Ferguson对通过收缩Petersen中三条完美匹配边得到的图作为禁止minor的图进行了完整地刻画。记P₀为Petersen收缩两条完美匹配边和一条非完美匹配边得到的子图基础上添加一条边得到的13条边的3-连通图。本文则主要完整地刻画了所有的4-连通P₀-minor-free图，并得到一个4-连通图G是P₀-minor-free图当且仅当它是平面图或属于 $\left\{K_6,K_6\backslash e,D{W}_4,C_5^2,C_7^2,K_{4,3}^4,K_{4,4}^{11}\right\}$ 。

然而本文对P₀-minor-free图的刻画也是仅限制在了4-连通图的刻画，后面还需要通过相关的链式定理将结果推广到3-连通图，这样才能够实现更完整地P₀-minor-free图的刻画。另外根据对称性，Petersen中收缩完美匹配边和非完美匹配边还有其他的方式，因此也可以考虑那些图作为禁止minor的图的刻画。

NOTES

^*通讯作者。