一类特殊坚韧图的性质

Properties of Some Class of Special Tough Graphs

摘要: 连通图G的坚韧度定义为。如果G的坚韧度是t，并且删去G的任意一条边后其坚韧度减小，则称G是极小t-坚韧的。Matthews等证明了K_1,3-free图的连通度是其坚韧度的2倍。本文证明了坚韧度为t的K_1,n-free图的连通度不超过(n-1)t，且极小1-坚韧，K_1,4-free图的连通度为2。此外，Kriesell猜想极小1-坚韧图的最小度是2。Katona等推广了上述猜想，极小t-坚韧图的最小度是 。本文证明了极小1/(n-1)-坚韧，K_1,n-free图的最小度为1，其中n≥3。

Abstract: The toughness of G is defined as . A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases the toughness. Matthews et al. has proved that the connectivity of K_1,3 -free graphs is twice its tough-ness. This paper shows that the connectivity of K_1,n -free graphs with toughness t is at most , and the connectivity of minimally 1-tough, K_1,4 -free graphs is 2. In addition, Kriesell con-jectured that the minimum degree of minimally 1-graphs is 2. Katona et al. proposed a generalized version of the conjecture that the minimum degree of minimally t-tough graph is . This paper proves that the minimum degree of minimally 1/(n-1)-tough, K_1,n -free graphs is 1, where n≥3 .

1. 引言

$G\left(V,E\right)$ 是无向，有限阶的简单图。对于G的任意一点v， $N_G\left(v\right)$ 是指G中相邻的点集， $d_G\left(v\right)$ 是指G中与v关联的边的数目。用 $\delta \left(G\right)$ 表示G的顶点的最小度，用 $\kappa \left(G\right)$ 表示G的连通度，且用 ${\kappa }^{\prime }\left(G\right)$ 表示G的边连通度。对于任意点集 $S\subseteq V\left(G\right)$，用 $G\left[S\right]$ 和 $G-S$ 分别表示S和 $V\left(G\right)-S$ 的导出子图，并且用 $w\left(G-S\right)$ 表示 $G-S$ 的分支个数。设S和T是G的子图或者 $V\left(G\right)$ 的子集，用 $N_S\left(T\right)$ 表示在 $S-T$ 中与T中点相邻的点集，用 $e\left(S,T\right)$ 表示S与T之间的边集。

定义1.1：设G是一个非完全连通图，其坚韧度定义为：

$\tau \left(G\right)=\min \left\{\left|S\right|/w\left(G-S\right):S\subseteq V\left(G\right),w\left(G-S\right)\ge 2\right\};$

如果G是完全图，则其坚韧度 $\tau \left(G\right)=+\infty$ ；如果G不连通，则其坚韧度 $\tau \left(G\right)=0$。

定义1.2：如果G的坚韧度为 $\tau \left(G\right)\ge t$，那么称G是t-坚韧的。若G的割集S满足 $\left|S\right|=\tau \left(G\right)\cdot w\left(G-S\right)$，则称S是G的坚韧集。

Chvátal [1] 在1973年首次提出坚韧度的定义，并提出了一个著名的猜想：存在正实数 $t_0$，使得每个 $t_0$ -坚韧图都是哈密顿图。之后，很多学者开始研究图的坚韧度和哈密顿图的关系。Thomassen给出了一个坚韧度为3/2的非哈密顿图：选择一个3-正则，3-连通且不存在哈密顿路的图G (Bermond [2] 证明了这样的图是存在的)，将图中的每个点都替换成三角形后得到图H，Chvátal [3] 证明了 $\tau \left(H\right)=3/2$，因此满足

Chvátal猜想的 $t_0>3/2$。之后，Bauer等在 [1] 中证明了，任给 $\epsilon >0$，都存在一个 $\left(\frac{9}{4}-\epsilon \right)$ -坚韧，不包含哈

密顿路的图，因此 $t_0>2$。在一些特殊的图类中，我们可以确定 $t_0$ 的值。例如，10-坚韧弦图 [4] 和3/2-坚韧分离图 [5] 是哈密顿图；4-坚韧，2k-连通 $P_2\cup 2P_1$ -free图 [6] 是哈密顿图；2-坚韧， $2K_2$ -free图 [7] 是哈密顿图；7-坚韧， $P_3\cup 2P_1$ -free图 [8] 是哈密顿图。此外，有些学者开始研究图的坚韧度和k-因子的关系 [9]。Enomoto等 [10] 给出了k-坚韧图有一个k-因子的充分条件是 $k\left|V\left(G\right)\right|$ 是偶数。Bauer等 [1] 证明了每个3/2-坚韧，5-弦图都有一个2-因子。1999年，Broersma [11] 在研究2-坚韧图的哈密顿性的过程中给出了极小t-坚韧图的定义。

定义1.3：如果G的坚韧度为t，且对于任意一条边 $e\in E\left(G\right)$ 都有 $\tau \left(G-e\right)<t$，则称G是极小t-坚韧的。

由坚韧度的定义可知每个t-坚韧非完全图都是2t-连通的，因此t-坚韧图的最小度至少是 $\lceil 2t\rceil$。在 [12] 中，Mader [13] 证明了极小k-连通图的最小度为k。据此，Kriesell [7] 针对极小1-坚韧图提出了以下猜想。后来，Katona [12] 推广了他的猜想。

猜想1.4： [14] 每个极小1-坚韧图都有一个2度顶点。

猜想1.5： [12] 每个极小t-坚韧图都有一个 $\lceil 2t\rceil$ 度顶点。

目前为止Kriesell的猜想还未被证明。2018年，Katona [12] 等给出了一个极小1-坚韧图最小度的上界，这是现在得到的最好的结果。虽然现在还没有证明Kriesell的猜想在所有图类上都成立，但是可以证明这个猜想在一些特殊图上成立，例如：Katona [12] 证明了极小1-坚韧， $K_{1,3}$ -free图的最小度是2。同样，推广的Kriesell猜想也被证明在一些特殊图类中成立。例如： [15] 中证明了极小t-坚韧弦图，分离图和 $K_{1,3}$ -free图的最小度为1，其中 $0<t\le 1/2$。

定理1.6： [12] 每个极小1-坚韧图最小度不超过 $3/n+1$。

根据极小t-坚韧图的定义，可以得到下面的命题。

命题1.7： [15] 设G是极小t-坚韧图，其中t是正实数。对于G的任意一条边e，

1) e是G的一条割边，或

2) 存在一个点集 $S=S\left(e\right)\subseteq V\left(G\right)$ 满足： $\left|S\right|\ge t\cdot w\left(G-S\right)$ 和 $\left|S\right|<t\cdot w\left(\left(G-e\right)-S\right)$，且e是 $G-S$ 的割边。

在第一种情况下，我们定义 $S=S\left(e\right)=\varnothing$。

本文主要研究t-坚韧， $K_{1,n}$ -free图的性质，并证明推广的Kriesell猜想在极小 $1/\left(n-1\right)$ -坚韧， $K_{1,4}$ -free图上成立。下面我们给出了 $K_{1,n}$ -free图的定义。

定义1.8：如果G不包含 $K_{1,n}$ 包含作为它的导出子图，则称G是 $K_{1,n}$ -free图。

2. 主要结论及其证明

2.1. t-坚韧， $K_{1,n}$ -Free图的连通度

在这一节中，我们研究t-坚韧， $K_{1,n}$ -free图的连通度。Matthews等 [16] 证明了 $K_{1,3}$ -free图的坚韧度和连通度有以下关系。

定理2.1： [16] 如果G是非完全 $K_{1,3}$ -free图，那么 $\kappa \left(G\right)=2\tau \left(G\right)$。

设 $n\ge 4$。对于 $K_{1,n}$ -free图，上述定理中的等式不成立。例如： $K_{n-1,n-1}$ 的坚韧度是1，但其连通度是 $n-1$，但其连通度是 $n-1$。下面我们给出了一个t-坚韧， $K_{1,n}$ -free图的连通度的上界。

定理2.2：设G是非完全 $K_{1,n}$ -free图，其中 $n\ge 4$。下面的结论成立。

(i) $\kappa \left(G\right)\le \left(n-1\right)\cdot \tau \left(G\right)$。

(ii) 如果 $\tau \left(G\right)=1$ 且 $n=4$，那么 $\kappa \left(G\right)=2$ 或者对于G的坚韧集S， $G-S$ 的每个分支在S中有且仅有三个邻点，且S中的每个点都与 $G-S$ 的每个分支相邻。

证明：由坚韧度的定义知，图G中存在割集S满足 $\left|S\right|\ge \tau \left(G\right)\cdot w\left(G-S\right)$。将 $G-S$ 的每个分支都收缩到一个点，用S表示这些点的集合，并将S与T之间的重边删掉。由于G是 $K_{1,n}$ -free图，所以S中的每个点都与T中的最多 $n-1$ 个邻点相邻，从而 $\left|e\left(S,T\right)\right|\le \left(n-1\right)\left|S\right|$。另一方面，由于T中的每个点在S中至少有 $\kappa \left(G\right)$ 个邻点，所以可以得到 $\left|e\left(S,T\right)\right|\ge \kappa \left(G\right)\cdot \left|T\right|=\kappa \left(G\right)\cdot w\left(G-S\right)$。因此 $\left(n-1\right)\left|S\right|\ge \kappa \left(G\right)\cdot w\left(G-S\right)$，从而 $\kappa \left(G\right)\le \left(n-1\right)\cdot \tau \left(G\right)$。

由上面的证明知，当 $\tau \left(G\right)=1$ 且 $n=4$ 时，有 $2=2\tau \left(G\right)\le \kappa \left(G\right)\le 3$。如果 $\kappa \left(G\right)=3$，由 $\tau \left(G\right)=1$ 知 $3\left|S\right|=\left|e\left(S,T\right)\right|=3\left|T\right|=3w\left(G-S\right)$。这时 $G-S$ 的每个分支在S中有且仅有三个邻点，且S中的每个点都与 $G-S$ 的每个分支相邻。

由上面的定理知，坚韧度为1的 $K_{1,4}$ -free图的连通度不一定为2，若Kriesell的猜想正确，则极小1-坚韧， $K_{1,4}$ -free图的连通度是2。

定理2.3：极小1-坚韧， $K_{1,4}$ -free图的连通度是2。

证明：设G是极小1-坚韧， $K_{1,4}$ -free图。假设 $\kappa \left(G\right)\ge 3$，由 $3\le \kappa \left(G\right)\le {\kappa }^{\prime }\left(G\right)$ 知中G没有割边。

任给边 $e=uv\in E\left(G\right)$，设 $S\left(e\right)\subseteq V\left(G\right)$ 是满足命题1.6的点集。由于e不是割边，所以 $S\left(e\right)\ne \varnothing$ 且 $\left|S\left(e\right)\right|=w\left(G-S\left(e\right)\right)$。这时 $\left|S\left(e\right)\right|>1$，否则 $S\left(e\right)\cup \left\{u\right\}$ 或 $S\left(e\right)\cup \left\{v\right\}$ 是G的一个二点割，这与 $\kappa \left(G\right)\ge 3$ 矛盾。因此 $w\left(G-S\left(e\right)\right)=\left|S\left(e\right)\right|\ge 2$，即 $S\left(e\right)$ 是G的坚韧集。设 $C\left(e\right)$ 是 $G-S\left(e\right)$ 中包含边e的分支，且 $C_u\left(e\right)$ 和 $C_v\left(e\right)$ 分别表示 $\left(G-e\right)-S\left(e\right)$ 中包含u和v的分支。由定理2.2 (ii)知，可设 $S^{\prime }\left(e\right)=N_{S\left(e\right)}\left(C\left(e\right)\right)=\left\{w_1,w_2,w_3\right\}$。若 $C_u\left(e\right)\ne \left\{u\right\}$，由 $\kappa \left(G\right)\ge 3$，容易得到 $\left|N_{S^{\prime }\left(e\right)}\left(C_u\left(e\right)-\left\{u\right\}\right)\right|\ge 2$ 且 $\left|N_{S^{\prime }\left(e\right)}\left(C_v\left(e\right)\right)\right|\ge 2$。再由 $\left|S^{\prime }\left(e\right)\right|=3$，可得 $N_{S^{\prime }\left(e\right)}\left(C_u\left(e\right)-\left\{u\right\}\right)\cap N_{S^{\prime }\left(e\right)}\left(C_v\left(e\right)\right)\ne \varnothing$。不妨设 $w_1\in N_{S^{\prime }\left(e\right)}\left(C_u\left(e\right)-\left\{u\right\}\right)\cap N_{S^{\prime }\left(e\right)}\left(C_v\left(e\right)\right)$。根据引理2.2 (ii)，点 $w_1$ 和 $G-S\left(e\right)$ 中除 $C\left(e\right)$ 外的另外两个分支相邻。显然， $G\left[N_{G-S\left(e\right)}\left(w_1\right)\right]$ 中包含一个 $K_{1,4}$ 子图，与G是 $K_{1,4}$ -free图矛盾。因此 $C_u\left(e\right)=\left\{u\right\}$。同理， $C_v\left(e\right)=\left\{v\right\}$。由于 $\delta \left(G\right)\ge \kappa \left(G\right)\ge 3$，我们可以设 $\left\{w_1,w_2\right\}\subseteq N_{S^{\prime }\left(e\right)}\left(u\right)$ 且 $\left\{w_1,w_3\right\}\subseteq N_{S^{\prime }\left(e\right)}\left(v\right)$。

令 $e_1=u{w}_1$。设 $S\left(e\right)\subseteq V\left(G\right)$ 是满足定理1.6的点集。类似于 $S\left(e\right)$ 的讨论，我们可以证明 $S\left(e_1\right)$ 也是G的坚韧集。显然， $v\in S\left(e_1\right)$。由定理2.2 (ii)知，点v与 $G-S\left(e_1\right)$ 的三个分支相邻。而 $N_G\left(v\right)\subseteq \left\{u\right\}\cup S^{\prime }\left(e\right)$，所以 $\left\{w_2,w_3\right\}\subseteq \left(G-S\left(e_1\right)\right)-C\left(e_1\right)$，这与 $u{w}_2\in E\left(G\right)$ 矛盾。

因此 $\kappa \left(G\right)\le 2$。再由 $\kappa \left(G\right)\ge 2\tau \left(G\right)=2$ 知 $\kappa \left(G\right)=2$。

2.2. 极小 $1/\left(n-1\right)$ -坚韧， $K_{1,n}$ -Free图

在这一节中，我们将研究极小 $1/\left(n-1\right)$ -坚韧， $K_{1,4}$ -free图的最小度。Katona等在 [4] [10] 中给出了极小1/2-坚韧和极小1-坚韧， $K_{1,3}$ -free图的结构。

定理2.4： [15] 极小1/2-坚韧， $K_{1,3}$ free图可以用下面的方式构造。

1) 任取一颗最大度为3的树，且树中所有3度点和1度点组成的点集是独立集。

2) 删掉每个度为3的点v，然后将v在树中每个邻点用一个三角形连接起来。

定理2.5： [12] 点数大于3的极小1-坚韧， $K_{1,3}$ -free图都是圈。

由上面的定理知，对于极小1/2-坚韧和极小1-坚韧， $K_{1,3}$ -free图，Kriesell的猜想是正确的。下面我们将研究，当 $n\ge 4$ 时，极小 $1/\left(n-1\right)$ -坚韧， $K_{1,n}$ -free图的最小度。由极小 $1/\left(n-1\right)$ -坚韧， $K_{1,4}$ -free图G的定义，容易得到以下引理。任给边 $e\in E\left(G\right)$，令 $k\left(e\right)=\min \left\{\left|S\left(e\right)\right|:S\left(e\right)是满足命题1.6的点集\right\}$。

引理2.6：设G是极小 $1/\left(n-1\right)$ -坚韧， $K_{1,n}$ -free图。对于G的任意一条非割边e，

(i) $k\left(e\right)=1$。

(ii) 有且仅有一个圈包含边e，且圈长为3。

证明：对于G的任意一条非割边e，由命题1.6知存在一个非空点集 $S\left(e\right)\subseteq V\left(G\right)$ 满足

$w\left(G-S\left(e\right)\right)\le \left(n-1\right)\left|S\left(e\right)\right|<w\left(\left(G-e\right)-S\left(e\right)\right)$。

这时 $w\left(G-S\left(e\right)\right)=\left(n-1\right)\left|S\left(e\right)\right|$。

将 $G-S\left(e\right)$ 的每个分支都收缩到一个点，用T表示这些点的集合，并将 $S\left(e\right)$ 与T之间的重边删掉。由于G是 $K_{1,n}$ -free图，所以S中的每个点都与T中的最多 $n-1$ 个邻点相邻，从而 $\left|e\left(S,T\right)\right|\le \left(n-1\right)\left|S\right|$。另一方面，由G是连通图知T中的每个点在 $S\left(e\right)$ 中至少有1个邻点，所以 $\left|e\left(S,T\right)\right|\ge \left|T\right|=\kappa \left(G\right)$。故有

$w\left(G-S\left(e\right)\right)=\left|T\right|\le \left|e\left(S\left(e\right),T\right)\right|\le \left(n-1\right)\left|S\left(e\right)\right|$。

由 $w\left(G-S\left(e\right)\right)=\left(n-1\right)\left|S\left(e\right)\right|$ 知 $\left|T\right|=\left|e\left(S\left(e\right),T\right)\right|=\left(n-1\right)\left|S\left(e\right)\right|$。因此 $G-S\left(e\right)$ 的每个分支在 $S\left(e\right)$ 中有且仅有一个邻点，且 $S\left(e\right)$ 中的每个点都与 $G-S\left(e\right)$ 的 $n-1$ 个分支相邻。

设 $C\left(e\right)$ 是 $G-S\left(e\right)$ 中包含边e的分支，令 $S^{\prime }\left(e\right)=N_{S\left(e\right)}\left(C\left(e\right)\right)=\left\{s_1\right\}$。因为在 $G-S\left(e\right)$ 中与 $s_1$ 相邻的 $n-1$ 个分支不与 $S\left(e\right)-\left\{s_1\right\}$ 中的点相邻，所以 $w\left(G-S^{\prime }\left(e\right)\right)=n-1$。不难看出 $S^{\prime }\left(e\right)$ 是满足命题1.6的点集，所以 $k\left(e\right)=1$ (见图1)。

Figure 1. $k\left(e\right)=1$

图1. $k\left(e\right)=1$

由于e是非割边，所以G中至少有一个圈包含边e。再由 $S^{\prime }\left(e\right)=\left\{s_1\right\}$ 知包含边e的圈一定包含 $s_1$。设e的两个端点分别是u和v。因为 $s_1$ 与 $G-S^{\prime }\left(e\right)$ 的 $n-1$ 个分支相邻且G是 $K_{1,n}$ -free的，所以 $N_{C\left(e\right)}\left(s_1\right)=\left\{u,v\right\}$，即e只包含在三角形 $uv{s}_1$ 中。

定理2.7：设 $n\ge 3$。极小 $1/\left(n-1\right)$ -坚韧， $K_{1,n}$ -free图的最小度是1。

证明：设G是极小 $1/\left(n-1\right)$ -坚韧， $K_{1,n}$ -free图。对于G的每个三角形，删掉三角形的三条边，然后增加一个点，将每个点与原来三角形的三个点连边。把G经过上述操作后得到的图记为H。由引理2.6 (ii)知G中的所有圈都是三角形，因此H是树。

下面我们将证明H中的每个叶子节点都是G中的1度点。假设H中存在一个叶子节点s不是G中的1度点。由H的构造过程知G中有且仅有一个三角形包含点s且 $d_G\left(s\right)=2$，设这个三角形的点集为 $\left\{u,v,s\right\}$。令 $e=uv$，设 $S\left(e\right)\subseteq V\left(G\right)$ 是满足命题1.6的点集，且 $\left|S\left(e\right)\right|=k\left(e\right)$。由引理2.6 (i)知 $S\left(e\right)=\left\{s\right\}$。由命题1.6知 $w\left(G-S\left(e\right)\right)=n-1$。由G是连通图且 $n\ge 4$，所以 $d_G\left(s\right)\ge n>3$，矛盾。

3. 结论

根据坚韧度的定义，我们可以得到t-坚韧图的连通度是2t-连通的，但是其连通度不一定为2t。对于一些特殊图类，我们可以确定图的坚韧度和连通度的关系。Matthews等 [16] 证明了坚韧度为t的 $K_{1,3}$ -free图的连通度是2t。由本文的定理2.2 (i)知，坚韧度小于2/3的 $K_{1,4}$ -free图的连通度为1，坚韧度大于等于2/3且小于1的 $K_{1,4}$ -free图的连通度是2且坚韧度为1的 $K_{1,4}$ -free图的连通度不超过3。Kriesell [14] 猜想极小1-坚韧图的最小度为2。由 $2\tau \left(G\right)\le \kappa \left(G\right)\le \delta \left(G\right)$ 知，如果Kriesell的猜想正确，容易推知极小1-坚韧图的连通度是2。本文证明了极小1-坚韧， $K_{1,4}$ -free图的连通度为2。Katona [12] 将Kriesell的猜想推广到了2t上。本文证明了对于极小 $1/\left(n-1\right)$ -坚韧， $K_{1,n}$ -free图，推广的Kriesell的猜想是正确的。

基金项目

山西省基础研究项目(20210302123097)。

NOTES

^*通讯作者。