子式极小的Super-5连通图 On the Minor Minimal Super 5-Connected Graphs

doi:10.12677/PM.2018.86098

Pure Mathematics
Vol. 08 No. 06 ( 2018 ), Article ID: 27839 , 7 pages
10.12677/PM.2018.86098

On the Minor Minimal Super 5-Connected Graphs

Chengfu Qin, Fenmei Mo^*

●How to Cite this Article

Department of Mathematics and Statistics, Guangxi Teachers Education University, Nanning Guangxi

Received: Nov. 10^th, 2018; accepted: Nov. 23^rd, 2018; published: Nov. 30^th, 2018

ABSTRACT

A graph H is called a minor of a graph G if H can be formed from G by deleting edges and vertices and by contracting edges. Let G be a k-connected graph such that G contains no other k-connected graph as its minor, then we call G a minor minimal k-connected graph. M. Kriesell showed that every minor hyper-5 connected graph has at most 12 vertices. In this paper, we show that every minor super-5 connected graph has at most 12 vertices.

Keywords:Super 5-Connected, Minor, Minimal, Characterization

子式极小的Super-5连通图

覃城阜，莫芬梅^*

广西师范学院，数学与统计科学学院，广西南宁

收稿日期：2018年11月10日；录用日期：2018年11月23日；发布日期：2018年11月30日

摘要

如果图G可以经过去边，或者去点，或者收缩子图得到子图H，则称H是G的子式。若G是k-连通图且G中不包含另外一个k-连通图作为子式，则称G是子式极小的k-连通图。M. Krisesell证明了子式极小的hyper-5连通图的顶点数至多是12。本文将这个结论推广到Super-5连通图。

关键词 :Super-5连通图，子式，极小，刻画

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在本文中我们考虑的都是有限阶，无向的简单图，未经说明的术语和记号我们参考 [1] 。设 $G = (V (G), E (G))$ ，其中 $V (G)$ 是G的顶点集， $E (G)$ 是G的边集。记 $| G | = | V (G) |$ 。若图G的任意顶点x与y都有连接x与y的路，则称G是连通图，否则G是不连通图，用 $κ (G)$ 表示G的连通度。对于连通图G， $T \subseteq V (G)$ 且 $G - T$ 至少有两个分支，则称T是G的一个点割。若T是G的点割并且 $| T | = κ (G)$ ，则称T是G的最小点割。设G是连通图， $T \subseteq V (G)$ 是G的最小点割。若A是 $G - T$ 若干个分支的并且 $G - T - A \neq ϕ$ ，则称T是A的断片。

在图G中与顶点x相邻的顶点称为x的邻点，x的所有邻点组成的集合称为x邻域，记为 $N (x)$ 。设

$A \subseteq V (G)$ ，记 $N (A) = \underset{x \in A}{\cup} N (x) - A$ 。我们用 $d (x) = | N (x) |$ 表示点x的度数，用 $V_{k} (G)$ 表示图G中所有度

数为k的顶点的集合。用 $Δ (G)$ 表示图G中的最大度， $δ (G)$ 表示图G中的最小度。 $S \subseteq V (G)$ ，我们用 $G [S]$ 表示集合S的诱导子图。

设 $e = x y$ 是图G的一条边，引进一个新的顶点 $v_{e}$ 使其与x和y的所有邻点都相邻，最后将x和y的去掉所得到的图称为是由图G收缩边e所得到的图，记为G/xy。设G是k-连通图， $e = x y$ 是图G的一条边。若G/xy还是k-连通图，则称e是G的k-可收缩边。若G是k-连通图且G的任意一条边e都有G/e不是k-连通图则称G是收缩临界k-连通图。若A是一个断片使得 $N (A)$ 中包含 $e \in F \subseteq E (G)$ ，则称A是相对于F的断片。特别地，当 $F = {e}$ 则称A是相对于e的断片.

由定义我们可知G是收缩临界k-连通图当且仅当对于任意 $e \in E (G)$ 都有e包含在一个最小点割内。

T是连通图G的最小点割，我们称T是一个shredder如果 $G - T$ 至少有3个分支。用 $ζ (G)$ 表示所有图G中的集shredder合。设 $S \in ζ (G)$ ，设 $G - S$ 有k个分支 $H_{1}, \dots, H_{k}$ 。不失一般性， $| H_{1} | \leq \dots \leq | H_{k} |$ 。记 $K (S) = {H_{k}}, L (S) = {H_{1}, \dots, H_{k - 1}}$ 。

一个k-连通图G如果满足：对于任意的最小点割T， $G - T$ 有一个分支是孤立点，则称G是Super-k连通图，简称G是Super的。若G是Super的且G中没有shredder，则称G是的hyper-k连通图。

我们可以将收缩边的概念作如下推广：对于k-连通图G的子图H，收缩H使指将H的每一个连通分支的边逐一收缩成一点，所得到的图记为G/H。若G/H仍是k-连通图，我们称H是G的k-可收缩子图。

对于图G和H，如果G可以经过如下一系列运算得到H：1) 去边；2) 去点；3)收缩子图，则称H是的子式G。若G是k-连通图且G不能通过上述的三种运算得到另一个k-连通图，则称G是子式极小的k-连通图。由定义可知，G是子式极小的k-连通图，则G一定是极小的k-连通图且也是收缩临界k-连通图。M. Kriesell证明了如下结论。

定理1.1 [2] ：设G是子式极小的5-连通图，若G是hyper5-连通图，则G最多有个12个顶点。

本文我们对收缩临界5-连通图的最小点割结构进行了研究，推广了M. Kriesell的结论，证明了如下结论。

定理1.2：设G是子式极小的5-连通图，若G是Super 5-连通图，则G最多有个12个顶点。

2. 定义与引理

我们知道子式极小的3-连通图是 $K_{4}$ ，子式极小的4-连通图是 $C_{6}^{2}$ 和 $K_{5}$ ，而子式极小的5-连通图有哪些目前还尚不清楚，而且要确定这些图也是比较困难。

引理2.1 [3] ：设G是收缩临界5-连通图， $x \in V (G)$ ， $d (x) \geq 6$ 。若 ${x_{1}, x_{2}} \in N (x) \cap V_{5} (G)$ 且 $x_{1} x_{2} \in E (G)$ ，则 $| N (x) \cap V_{5} (G) | \geq 3$ 。

引理2.2 [3] ：设G是收缩临界5-连通图， $x \in V (G)$ ，A是G中的断片且 $x \in N (A)$ 。

若 $| A | \geq 3$ ， $| \bar{A} | \geq 2$ 并且 $N (x) \cap A = {y}$ ，则有 $N (A)$ 存在一个5度点z与x相邻，而且满足 $N (x) \cap A \subseteq N (z) \cap A$ 且 $| N (z) \cap A | \geq 2$ 。特别地，当 $d (y) \geq 6$ 时，则有 $| d (z) \cap \bar{A} | = 1$ 。

引理2.3：设G是收缩临界5-连通图， $A = {x, y}$ 是G的一个断片。令B是相对于xz断片，这里 $z \in N (A) \cap N (x)$ 。如果 $N (A) - {z} \subseteq N (y)$ ，则有 $A \subseteq N (B)$ 。

引理2.4 [4] ：设G是收缩临界5-连通图，A是G的一个断片，使得 $| A | = 2$ 且有一个6度点，则 $N (A)$ 至少有三个5度点。

引理2.5 [4] ：设G是收缩临界5-连通图， $x \in V_{6} (G)$ ，令 $ξ_{x} = {{x, y} | y \in N (x)}$ 。若A为 $ξ_{x}$ -原子，则 $| A | \leq 2$ 。

引理2.6 [4] ：设G是收缩临界5-连通图且 $| G | \geq 10$ ， $A = {u, y}$ 是G的断片， $N (A) = {x, w_{1}, w_{2}, w_{3}, w_{4}}$ 。若 $d (u) = d (w_{i}) = 5, (i = 1, 2, 3, 4)$ ， $x u \notin E (G)$ ，则 $H_{0} = G [{w_{1}, w_{2}, w_{3}, w_{4}}] ≅ 2 K_{2}$ 。

引理2.7 [4] ：设G是收缩临界5-连通图， $S \in ζ (G)$ ，若 $L (S)$ 有一个元素的阶至少为2，则 $L (S)$ 的每个元的阶至少为4。

引理2.8 [5]：设G是收缩临界5-连通图， $V_{5} (G)$ 表示G中的5度顶点的集合。设T是G的最小点割，A是T-断片且 $| A | \geq 2$ 。如果T中存在 $t_{1} \neq t_{2}$ ，使得 $| N (t_{1}) \cap A | = | N (t_{2}) \cap A | = 1$ ，则T中存在一点 $t \in V_{5} \cap (T - {t_{1}, t_{2}})$ ，使得 $t_{1}$ 或者 $t_{2}$ 与t相邻且 $A \subseteq N (t)$ 。

引理2.9 [4] ：设G是子式极小5-连通图且 $| V (G) | \geq 10$ ，则 $V_{\geq 6} (G)$ 无边导出子图。

引理2.10 [4]：设G是收缩临界5-连通图，设A为G的断片， $x \in N (A)$ 且 $N (x) \cap N (A) \neq ϕ$ 。若 $| \bar{A} | \geq 2$ ，则 $A \cup T_{A}$ 中包含x的一个5度点邻域。

引理2.11 [4] ：设G是收缩临界k-连通图，R是shredder，令 $C_{1}, C_{2} \in L (R)$ ，使得 $| C_{1} | = | C_{2} | = 1$ 。设
$C_{1} = {x}$ ， $C_{2} = {y}$ ，则 $G + x y$ 仍是收缩临界k-连通图。

在本文的证明中，我们会反复用到下面断片的结论：

引理2.12 [6] ：若A，B为G的两个不同的断片， $T_{A} = N (A)$ ， $T_{B} = N (B)$ ，那么：

1) 若 $A \cap B \neq ϕ$ ，则 $| A \cap T_{B} | \geq | T_{A} \cap \bar{B} |$ ， $| T_{A} \cap B | \geq | \bar{A} \cap T_{B} |$ ；

2) 若 $A \cap B \neq ϕ \neq \bar{A} \cap \bar{B}$ ，则 $A \cap B$ 和 $\bar{A} \cap \bar{B}$ 都是G的断片，且 $N (A \cap B) = (T_{A} \cap B) \cup (T_{A} \cap T_{B}) \cup (A \cap T \cap B)$ ； $N (\bar{A} \cap \bar{B}) = (T_{A} \cap \bar{B}) \cup (T_{A} \cap T_{B}) \cup (\bar{A} \cap T_{B})$ ；

3) 若，且 $A \cap B$ 不是断片，则有 $\bar{A} \cap \bar{B} = ϕ$ ，且 $| A \cap T_{B} | > | T_{A} \cap \bar{B} |$ ， $| T_{A} \cap B | > | \bar{A} \cap T_{B} |$ 。

引理2.13 [4] ：设A为G的断片， $T_{A} = N (A) ， S \subseteq N (A)$ 。若 $| N (S) \cap A | < | S |$ , 则A = N(S)。

3. 主要结果证明

引理3.1：设G是收缩临界5-连通图， $| V (G) | \geq 10$ ， $A = {x, y}$ 是G的断片， $N (A) = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}}$ ， ${x, y} \cap V_{5} (G) = ϕ$ 。令 $H = G [N (A) \cap V_{5} (G)]$ ，则

1) $| H | \geq 4$ ；

2) $e (H) \geq 2$ ， $H \supseteq 2 K_{2}$ ；

3) H中没有长为3的路；

若 $e (H) \geq 3$ ，则， $G [N (A)] ≅ P_{1} \cup P_{2}$ 。

证明：1) 由引理2.4，知 $N (A)$ 中至少有三个5度点。不妨设 ${x_{1}, x_{2}, x_{3}} \subseteq V_{5} (G)$ 。若 ${x_{4}, x_{5}} \cap V_{5} (G) = ϕ$ ，我们将导出矛盾。

断言1： $N (x_{4}) \cap {x_{1}, x_{2}, x_{3}} \neq ϕ$ ， $N (x_{5}) \cap {x_{1}, x_{2}, x_{3}} \neq φ$ 。

我们只证明 $N (x_{4}) \cap {x_{1}, x_{2}, x_{3}} \neq φ$ 。对于 $x_{5}$ 也可以类似证明。

如若不然，设 $x_{4}$ 不与 $N (A)$ 中的5度点相邻。设 $B_{1}$ 是相对于 $x x_{4}$ 的断片。由引理2.3，我们有 $A \subseteq N (B_{1})$ 。又由假设，我们有 $| B_{1} \cap N (A) | = | {\bar{B}}_{1} \cap N (A) | = 2$ 。不失一般性，设 $B_{1} \cap N (A) = {x_{1}, x_{5}}$ 。于是 $x_{1}$ 在 $N (A)$ 中不与5度点相邻。令 $B_{2}$ 是相对于 $x x_{1}$ 的断片，同样由引理2.3，知 $A \subseteq N (B_{2})$ 。类似地，我们有 $| B_{2} \cap N (A) | = | {\bar{B}}_{2} \cap N (A) | = 2$ 。不失一般性，设 $x_{4} \in B_{2} \cap N (A)$ 。

若 $x_{5} \in B_{2} \cap N (A)$ ，考察 $B_{1}, B_{2}$ ，我们有 ${x, y} \in N (B_{1}) \cap N (B_{2})$ ， $x_{5} \in B_{1} \cap B_{2}$ ， ${x_{2}, x_{3}} \subseteq {\bar{B}}_{1} \cap {\bar{B}}_{2}$ 且 $x_{1} \in B_{1} \cap N (B_{2})$ ， $x_{4} \in B_{2} \cap N (B_{1})$ 。由引理2.12可知 $B_{1} \cap B_{2}$ 和 ${\bar{B}}_{1} \cap {\bar{B}}_{2}$ 都是G的断片。所以 $N ({x, y}) \cap (B_{1} \cap B_{2}) = {x_{5}}$ ，由引理2.3， $B_{1} \cap B_{2} = {x_{5}}$ 。于是 $d (x_{5}) = 5$ ，矛盾。

若 $x_{5} \in {\bar{B}}_{2} \cap N (A)$ ，不失一般性设 $x_{2} \in B_{2} \cap N (A)$ 。此时考察 $B_{1}, B_{2}$ ，我们同样可得 $d (x_{5}) = 5$ ，矛盾。所以断言1成立。

不妨设 $x_{4} x_{1} \in E (G)$ 。若 $x_{5} x_{1} \in E (G)$ ，则 $| N (x_{1}) \cap \bar{A} | = 1$ 且 $N (x_{1}) \cap N (A) = {x_{4}, x_{5}}$ 。注意到 $| \bar{A} | \geq 3$ ，由引理2.2， $d (x_{4}) = 5$ 或 $d (x_{5}) = 5$ ，矛盾。所以 $x_{5} x_{1} \notin E (G)$ ，不妨设 $x_{5} x_{2} \in E (G)$ 。

断言2：且 $x_{3} x_{2} \notin E (G)$ 。

不妨设 $x_{3} x_{1} \in E (G)$ ，则 $| N (x_{1}) \cap \bar{A} | = 1$ ， $N (x_{1}) \cap N (A) = {x_{4}, x_{3}}$ 。由引理2.2，知 $| N (x_{3}) \cap \bar{A} | = 2$ ， $N (x_{3}) N (A) = {x_{1}}$ 且 $N (x_{1}) \cap \bar{A} \subseteq N (x_{3}) \cap \bar{A}$ 。令 $B_{4}$ 是相对于 $x x_{2}$ 的断片，显然有 $A \subseteq N (B_{4})$ 。注意到 $N (x_{1}) \cap N (A) = {x_{4}, x_{3}}$ ， $N (x_{3}) \cap N (A) = {x_{1}}$ ，我们有 $N (x_{2}) \cap V_{5} (G) \cap N (A) = ϕ$ 。于是 $| B_{2} \cap N (A) | = | {\bar{B}}_{2} \cap N (A) | = 2$ 。这与 $x_{3} x_{1} x_{4}$ 是长为2的路，矛盾。所以 $x_{3} x_{1} \notin E (G)$ ，类似地 $x_{3} x_{2} \notin E (G)$ 。

由引理2.10，有 $x_{1} x_{2} \in E (G)$ 。于是 $| N (x_{1}) \cap \bar{A} | = 1$ ， $| N (x_{2}) \cap \bar{A} | = 1$ 且 $N (x_{1}) \cap N (A) = {x_{2}, x_{4}}$ ， $N (x_{2}) \cap N (A) = {x_{1}, x_{5}}$ ，由引理2.2可以导出矛盾。于是1)成立。

类似于引理2.6的证明，我们有2)的成立。由1)不妨设 ${x_{1}, x_{2}, x_{3}, x_{4}} \subseteq V_{5} (G)$ 。

下面我们来证明3)。反证法，不妨设 $x_{1} x_{2} x_{3} x_{4}$ 是H中长为3的路，则 $| N (x_{1}) \cap \bar{A} | = 1$ ， $| N (x_{3}) \cap \bar{A} | = 1$ 。此时我们主要到 $N (x_{1}) \cap N (A) = {x_{2}, x_{3}}$ ， $N (x_{3}) \cap N (A) = {x_{1}, x_{4}}$ 。由引理2.2，我们知 $| N (x_{1}) \cap \bar{A} | = 2$ ， $| N (x_{4}) \cap \bar{A} | = 2$ 。此时显然 $x_{5}$ 在 $N (A)$ 中没有邻点。

令 $B_{5}$ 是相对于 $x x_{5}$ 的断片，易见 $A \subseteq N (B_{5})$ 。由于 $x_{5}$ 在 $N (A)$ 中没有邻点，有 $| B_{2} \cap N (A) | = | {\bar{B}}_{2} \cap N (A) | = 2$ 。这与 $x_{1} x_{2} x_{3} x_{4}$ 是H中长为3的路，矛盾。所以3)成立。

由2)，我们设 $x_{1} x_{2}$ 和 $x_{3} x_{4}$ 是H的两条边。由3)， ${x_{1}, x_{2}}$ 与 ${x_{3}, x_{4}}$ 之间没有边。即 $G [{x_{1}, x_{2}, x_{3}, x_{4}}] ≅ 2 K_{2}$ 。所以当 $e (H) \geq 3$ 时我们有 $N (A) \subseteq V_{5} (G)$ 且 $G [N (A)] ≅ P_{1} \cup P_{2}$ ，故4)成立。于是引理3.1成立。

故对G收缩临界5-连通图， $| V (G) | \geq 10$ ， $A = {x, y}$ 是G的断片， $N (A) = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}}$ ， ${x, y} \cap V_{5} (G) = ϕ$ ，则由引理3.1，不妨设 ${x_{1}, x_{2}, x_{3}, x_{4}} \subseteq V_{5} (G)$ 且 $x_{1} x_{2} \in E (G)$ ， $x_{3} x_{4} \in E (G)$ 。此时易见 ${x_{1}, x_{2}}$ 与 ${x_{3}, x_{4}}$ 之间没有边。

若 $G [N (A)]$ 是连通图，则由引理3.1，我们有 $d (x_{5}) \geq 6$ ， $G [N (A)]$ 是路且易见 $x_{5}$ 是 $G [N (A)]$ 的中心。

若 $G [N (A)]$ 有两个分支，不妨设 $x_{1} x_{2}$ 是其中一个分支，则另一个分支也是一条路。

由上面的结论，我们取H中的一条边，不妨设为 ${x_{1}, x_{2}}$ ，使得 $x_{5}$ 与 ${x_{1}, x_{2}}$ 之间的边尽可能的少。于是若 $x_{5}$ 与 ${x_{1}, x_{2}}$ 之间有边，则其与 ${x_{3}, x_{4}}$ 之间也有边。

引理3.2：令 $G_{3} = G / {x x_{1}, y x_{2}}$ ，则 $G_{3}$ 是5-连通图。

证明：令 ${x^{'}}_{1}, {x^{'}}_{2}$ 是G分别收缩 $X X_{1}, Y X_{2}$ 后得到的新顶点。

断言1 $δ (G_{3}) \geq 5$ 。

若 $x_{5}$ 与 ${x_{1}, x_{2}}$ 之间没有边，则易见 $δ (G_{3}) \geq 5$ 。

若 $x_{5}$ 与 ${x_{1}, x_{2}}$ 之间有边，则由 ${x_{1}, x_{2}}$ 的选择，我们不妨设 $x_{2} x_{5} \in E (G)$ ， $x_{3} x_{5} \in E (G)$ 。此时 $G [N (A)] ≅ P$ ，这里 $P = x_{1}, x_{2}, x_{3}, x_{4}, x_{5}$ 是一条路。同样可得 $δ (G_{3}) \geq 5$ 。

断言2： $k (G_{3}) \geq 4$ 且 $k (G_{3}) = 4$ 时， ${{x^{'}}_{1}, {x^{'}}_{2}}$ 包含在 $G_{3}$ 的每一个最小点割内。

若 $k (G_{3}) \leq 4$ ，令是阶为3的最小断片。由 $k (G) = 5$ ，我们有 ${{x^{'}}_{1}, {x^{'}}_{2}} \subseteq T^{'}$ 。令 $B^{'}$ 是 $G_{3}$ 的 $T^{'}$ -断片。由 $δ (G_{3}) \geq 5$ ，我们有 $| B^{'} | \geq 3$ ， $| \bar{B^{'}} | \geq 3$ 。令T是将 $T^{'}$ 恢复后所得到的集合。显然， $| T | = 5$ ， ${x, x_{1}, y, x_{2}} \subseteq T$ 。另外易见 $B = B^{'}, \bar{B} = \bar{B^{'}}$ 是G中的 $T^{'}$ -断片。所以 $| N (x) \cap T | \geq 3$ 。于是由 $d (x) = 6$ 可知 $| N (x) \cap B | = 1$ 或 $| N (x) \cap \bar{B} | = 1$ 。不妨设 $| N (x) \cap B | = 1$ 。此时由 $N (x) - {y} = N (y) - {x}$ ，我们有 $| N (y) \cap B | = 1$ ， $N (y) \cap B = N (x) \cap B$ 。则由引理2.1， $| B | = 1$ ，矛盾。所以 $k (G_{3}) \geq 4$ 。

若 $k (G_{3}) = 4$ ，令 $T^{'}$ 是 $G_{3}$ 的最小点割， $B^{'}$ 是 $G_{3}$ 的 $T^{'}$ -断片。由于 $δ (G_{3}) \geq 5$ ， $| B^{'} | \geq 2$ ， $| \bar{B^{'}} | \geq 2$ 。令T是将 $T^{'}$ 恢复后所对应的集合。显然由 $k (G) = 5$ 我们有 ${{x^{'}}_{1}, {x^{'}}_{2}} \cap T^{'} \neq ϕ$ 。若 ${{x^{'}}_{1}, {x^{'}}_{2}} ⊄ T^{'}$ ，不妨设 ${x^{'}}_{2} \in T^{'}, {x^{'}}_{1} \in B^{'}$ 。

令B是将 $B^{'}$ 恢复后所对应的集合。显然可得， $| T | = 5$ ， ${y, y_{2}} \subseteq T$ ， ${x, x_{2}} \subseteq B$ 。由 $N (x) - {y} = N (y) - {x}$ ，我们有 $N (y) \cap \bar{B} = ϕ$ ，矛盾。所以断言2成立。

下面我们来证 $k (G_{3}) = 5$ 。如若不然，令 $T^{'}$ 是 $G_{3}$ 的最小点割， $B^{'}$ 是 $G_{3}$ 的 $T^{'}$ -断片。则由 $δ (G_{3}) \geq 5$ ，我们有 $| B^{'} | \geq 2$ ， $| \bar{B^{'}} | \geq 2$ 。令T是将 $T^{'}$ 恢复后所对应的集合。由断言2， ${{x^{'}}_{1}, {x^{'}}_{2}} \subseteq T^{'}$ 。于是 $| T | = 6$ ， ${y, x, x_{1}, x_{2}} \subseteq T$ 。记 $B = B^{'}$ 是 $G - T$ 的一部分。这里为方便讨论，我们仍然记 $\bar{B} = G - T - B$ 。由 $N (x) - {y} = N (y) - {x}$ ，我们有 $N (x) \cap B \neq ϕ$ ， $N (x) \cap \bar{B} \neq ϕ$ 。由对称性，设 $x_{3} \in B, x_{5} \in \bar{B}$ 。下面分两种情况讨论。

情况1： $G [{x_{3}, x_{4}, x_{5}}]$ 不连通。由 $x_{3} \in B, x_{5} \in \bar{B}$ ，则 $x_{4} x_{5} \in E (G)$ ， $x_{4} \in T$ 。此时有 $d (x_{4}) = 5$ 以及 $| N (x_{4}) \cap T | = 2$ ， $| N (x_{4}) \cap B | \leq 1$ ，或者 $| N (x_{4}) \cap \bar{B} | \leq 1$ 。不妨设 $| N (x_{4}) \cap B | \leq 1$ ，则 $N (x_{4}) \cap B = {x_{3}}$ 。于是 $(T - {x, y, x_{4}}) \cup {x_{3}}$ 是G阶为4的点割，矛盾。

情况2： $G [{x_{3}, x_{4}, x_{5}}]$ 不连通。

则由 ${x_{1}, x_{2}}$ 的选择， $x_{5}$ 在 $N (A)$ 中没有邻点。

若 $| B | = 2$ ，则 $B = {x_{3}, t}$ 。由 ${x_{1}, x_{2}}$ 与 ${x_{3}, x_{4}}$ 之间没有边，有 $t \neq x_{4}$ 。于是 $x_{4} \in T$ 。

由 $x_{5}$ 在 $N (A)$ 中没有邻点，有 $| \bar{B} | \geq 3$ ，显然 $d (t) = 5$ 且 $t x_{4} \in E (G)$ 。令 $B_{1} = \bar{B} - {x_{5}}$ ，则 $N (B_{1}) = {x_{5}} \cup (T - {x, y})$ ， $| N (B_{1}) | = 5$ ，。又由于 $N (x_{4}) \cap {\bar{B}}_{1} = {x_{3}, t, x, y}$ ，我们有 $N (x_{4}) \cap N ({\bar{B}}_{1}) = ϕ$ ， $| N (x_{4}) \cap B_{1} | = 1$ ， $| {\bar{B}}_{1} | \geq 3$ 。若 $| B_{1} | \geq 3$ ，由引理2.2可得到矛盾。

所以设 $| B_{1} | = 2$ 。注意到 $t \in N (x_{1}) \cap N (x_{2})$ ，则 $| N (x_{1}) \cap B_{1} | = 1$ ， $| N (x_{2}) \cap B_{1} | = 1$ 。 ${x_{1}, x_{2}}$ 与 $N (B_{1}) - {x_{1}, x_{2}}$ 之间没有边。若 $N (x_{1}) \cap B_{1} = N (x_{2}) \cap B_{1}$ ，由引理2.2得， $| B_{1} | = 1$ ，矛盾。

若 $N (x_{1}) \cap B_{1} \neq N (x_{2}) \cap B_{1}$ ，则由引理2.8得， $N (B_{1}) - {x_{1}, x_{2}}$ 与 ${x_{1}, x_{2}}$ 之间没有边，矛盾。

所以设 $| B | \geq 3$ 。若 $| \bar{B} | = 2$ ，令 $\bar{B} = {x_{5}, h}$ 。由 $T - {x_{1}, x_{2}} \subseteq N (x_{5})$ ，以及 $x_{5}$ 在 $N (A)$ 中没有邻点，我们有 $x_{4} \in N (B)$ 。令 $T = {x_{1}, x_{2}, x, y, z, w}$ ，显然易见 $N (h) = {x_{1}, x_{2}, x_{5}, z, w}$ ， $N (x_{5}) = {x, y, h, z, w}$ 。

令C是G的相对于 $x x_{5}$ 的断片，显然 $A \subseteq N (C)$ 。又由 $x_{5}$ 在 $N (A)$ 中没有邻点， $| C \cap N (A) | = | \bar{C} \cap N (A) | = 2$ 。不妨设 $C \cap N (A) = {x_{1}, x_{2}}$ ， $\bar{C} \cap N (A) = {x_{3}, x_{4}}$ 。由G是5-连通图我们有， $C \cap \bar{A} = ϕ$ ， $\bar{C} \cap \bar{A} = ϕ$ 。故 $C \cap \bar{A}$ ， $\bar{C} \cap \bar{A}$ 都是G的断片。所以 $N (x_{5}) \cap C \cap \bar{A} \neq ϕ$ 。此时易见 $h \in N (C) \cap \bar{A}$ 。我们不妨设 $N (x_{5}) \cap \bar{C} \cap \bar{A} = {z}$ ， $N (x_{5}) \cap C \cap \bar{A} = {w}$ 。由 ${x_{1}, x_{2}} \subseteq N (h)$ ， $N (h) \cap C \cap \bar{A} = {w}$ 。于是 $N ({x_{5}, h}) \cap \bar{C} = {w}$ 。由引理2.1， $\bar{C} = {w}$ ， ${x_{1}, x_{2}} \subseteq N (w)$ 。故 $N (x_{1}) \cap B = ϕ$ ， $N (x_{2}) \cap B = ϕ$ 。因此是 $T - {x_{1}, x_{2}}$ 是G的4-点割，矛盾。

所以我们设 $| \bar{B} | \geq 3$ ， $| B | \geq 3$ 。

注意到 $N (x) \cap \bar{B} = {x_{5}} = N (y) \cap \bar{B}$ 。当 $N (x_{1}) \cap B = ϕ$ ，则 $T \cup {x_{3}} - {x, y, x_{1}}$ 是G的4-点割，矛盾。所以 $N (x_{1}) \cap B \neq ϕ$ ，类似的有 $N (x_{2}) \cap B \neq ϕ$ 。于是 $| N (x_{1}) \cap B | \leq 1$ ， $| N (x_{2}) \cap B | \leq 1$ 。若 $| N (x_{1}) \cap B | = 0$ ，则B是G的断片， $N (B) = T - {x_{1}}$ 。则有 $| N (x_{2}) \cap B | = 1$ ， $N (x_{2}) \cap N (B) = {x, y}$ 。此时对 $x_{2}$ 和B应用引理2.2可导矛盾。所以 $| N (x_{1}) \cap B | = 1$ ，类似地有 $| N (x_{1}) \cap B | = 1$ 。于是 $| N (x_{1}) \cap \bar{B} | = 1$ ， $| N (x_{2}) \cap \bar{B} | = 1$ 。令 $B_{3} = \bar{B} - {x_{5}}$ ，则 $| N (B_{3}) | = 5$ ， $N (x_{1}) \cap N (B_{3}) = {x_{2}}$ ， $N (x_{2}) \cap N (B_{3}) = {x_{1}}$ 。由 $| B_{3} | \geq 2$ 以及引理2.1，我们有 $N (x_{1}) \cap N (B_{3}) \neq N (x_{2}) \cap N (B_{3})$ 。若 $| B_{3} | = 2$ ，则由引理2.8， $N (B_{3}) - {x_{1}, x_{2}}$ 中存在一个点与 $x_{1}$ 或 $x_{2}$ 相邻，矛盾。若 $| B_{3} | \geq 3$ ，对 $x_{2}$ 和 $B_{3}$ 应用引理2.2可导出矛盾。

引理3.3 设G是子式极小5-连通图，且 $S \in Γ$ 是5-shredder，则 $S = N (x)$ ，这里 $x \in V_{5} (G)$ 。

证明：显然，G收缩临界极小5-连通图。令 $A, B, C$ 是 $G - S$ 的三个分支。若A，B或C中有一个阶为1，则结论成立。于是设 $| A | \geq 2$ ， $| B | \geq 2$ ， $| C | \geq 2$ 。由推论2.7， $G - S$ 的每一个分的阶至少为4。记 $S = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}}$ 。令 $G_{1} = G / A$ ，我们将证明 $G_{1}$ 是5-连通图。这与G是子式极小，矛盾。

断言1： $S \cap V_{5} (G) = ϕ$ 。

否则 $d (x_{1}) = 5$ 。由于 $G - S$ 有至少三个断片，于是 $G - S$ 至少有一个断片只含 $x_{1}$ 的一个邻点。不妨设 $| N (x_{1}) \cap A | = 1$ ，则由引理2.2， $N (A)$ 中存在一个5度点，设为 $x_{2}$ ，使得 $x_{1} x_{2} \subseteq E (G)$ 且 $| N (x_{2}) \cap A | \geq 2$ 。由 $d (x_{2}) = 5$ ，我们有 $| N (x_{2}) \cap B | = 1$ ， $| N (x_{2}) \cap C | = 1$ ， $| N (x_{2}) \cap S | = {x_{1}}$ 。同样由引理2.2， $| N (x_{1}) \cap B | \geq 2$ ， $| N (x_{1}) \cap C | \geq 2$ 。于是 $d (x_{1}) \geq 1 + 1 + 2 + 2 = 6$ ，矛盾。所以断言1成立。

由引理2.9以及断言1，我们有 $E (G [S]) = 0$ 。

断言2： $x_{i}, i = 1, 2, 3, 4, 5$ 在的每个分支内至少有两个邻点。

否则不妨设 $| N (x_{1}) \cap A | = 1$ ，则由引理2.2可知 $N (A)$ 中存在一个5度点，矛盾。

由断言1以及断言2，我们有 $δ (G_{1}) \geq 5$ 且 $E (G_{1} [S]) = 0$ 。令a将A收缩后得到的点。

下面我们来证明 $κ (G_{1}) = 5$ 。否则，设 $T^{'}$ 是 $G_{1}$ 中阶为4的点割，D是 $G_{1}$ 的 $T^{'}$ -断片。由 $δ (G_{1}) \geq 5$ ，我们有 $| D | \geq 2$ 。

显然 $a \in T^{'}$ 。我们设 $T^{'} = {x, y, z, a}$ 。于是有 $| N (a) \cap D | \geq 2$ ， $| N (a) \cap \bar{D} | \geq 2$ (否则，不妨设 $| N (a) \cap D | \leq 1$ ，则 $D^{'} = D - N (a)$ 是 $G_{1}$ 的一个断片且 $a \notin N (D^{'})$ ，此时易见 $N (D^{'})$ 是G的4点割，矛盾)。不妨设 ${x_{1}, x_{2}} \subseteq D$ ， ${x_{3}, x_{4}} \subseteq \bar{D}$ 。由 $B, C$ 是 $G - S$ 的连通分支，我们有 $C \cup S$ 和 $B \cup S$ 都有路连接 $x_{i}$ 和 $x_{j}, i \neq j$ 且 $i, j \in {1, 2, 3, 4, 5}$ 。故 ${x, y, z} \cap C \neq ϕ$ 。

于是我们有 $| {x, y, z} \cap B | = 1$ 或 $| {x, y, z} \cap C | = 1$ 。不妨设 $| {x, y, z} \cap B | = 1$ 且 $x \in B$ 。此时由断言2，我们有 $B - {x}$ 可以分成两子图 $B_{1}$ 和 $B_{2}$ ，使得 $N (x_{i}) \cap N (B_{2}) = ϕ, i = 1, 2$ ， $N (x_{i}) \cap B_{1} = ϕ, i = 3, 4$ 。于是我们有 $S \cup {x} - {x_{3}, x_{4}}$ 是G的一个4点割，矛盾。

推论3.1：设G是子式极小的5-连通图且有 $| V (G) | \geq 10$ 。则对任意最小点割T，则 $G - T$ 恰好有两个分支。特别的，若G还是Super5-连通，则G一定是hyper5-连通。

证明：由定义，G是收缩临界的极小5-连通图。若 $G - T$ 有至少3个分支。令A，B和C是 $G - T$ 的3个分支。由引理2.7和引理3.3我们有 $G - T$ 恰好有3个分支且有两个分支只有一个点。不妨设 $| B | = | C | = 1$ ， $B = {x}$ ， $C = {y}$ 。由引理2.10， $G + x y$ 仍然是收缩临界5-连通图。于是在 $G + x y$ 中， $D = {x, y}$ 是 $G + x y$ 的一个断片，且x和y在 $G + x y$ 中的度为6。设 $N (A) = {x_{1}, \dots, x_{5}}$ ，我们如引理3.2选取 $x_{1}, x_{2}$ 。则由引理3.2， $G + x y / {x x_{1}, y x_{2}}$ 是5-连通图。又 $x_{1} x_{2} \subseteq E (G)$ ，我们有 $G + x y / {x x_{1}, y x_{2}}$ $G / {x x_{1}, y x_{2}}$ ，这与G是子式极小，矛盾。于是 $G - T$ 恰好有两个分支，当G还是Super5-连通，显然可知，G是hyper5-连通。

由定理1.1以及推论3.1，我们可知定理1.2成立。

基金项目

国家自然科学基金资助项目：11401119。

文章引用

覃城阜,莫芬梅. 子式极小的Super-5连通图
On the Minor Minimal Super 5-Connected Graphs[J]. 理论数学, 2018, 08(06): 730-736. https://doi.org/10.12677/PM.2018.86098

参考文献

1. Bondy, J.A. and Murty, S.R. (1976) Graph Theory with Alications. MacMillan.

2. Kriesell, M. (2007) How to Contract an Essen-tially 6-Connected Graph to a 5-Connected Graph. Discrete Mathematics, 307, 494-510.
https://doi.org/10.1016/j.disc.2005.09.040

3. 覃城阜. 收缩临界5-连通图的性质[D]: [硕士学位论文]. 桂林: 广西师范大学, 2004.

4. 覃城阜. 5-连通图的可收缩子图及minors [D]: [博士学位论文]. 厦门: 厦门大学, 2010.

5. Kriesell, M. (2005) Triangle Density and Contractibility. Combinatorics, Probability and Computiny, 14, 133-146.

6. Kriesell, M. (2001) A Degree Sum Contio for the Existence of Contraciable Edge in k Connected Graph. Journal of Combinatorial Theory, Series B, 82, 81-101.

期刊菜单