几类极小t-坚韧图的构造

The Construction of Some Classes of Minimally t-Tough Graphs

摘要: 若图G的坚韧度为t，且删除G中任意一条边后坚韧度减小，则称图G是极小t-坚韧的。构造极小t-坚韧图并研究其结构特性在理论和应用上都具有重要意义。证明了几类笛卡尔积图和线图的极小t-坚韧性，并构造出一类k-正则的极小k/2-坚韧图。

Abstract: 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. Constructing a minimally t-tough graph and studying its structural characteristics are of great significance in theory and applications. This paper proves that several kinds of Cartesian product graphs and line graphs are minimally t-tough and also construct a class of k-regular, and minimally k/2-tough graphs.

1. 引言

1973年，Chvátal [1] 首次提出坚韧度的概念，用于研究图的哈密尔顿性。后来，坚韧度成为一个重要的网络抗毁性参数。

定义1 [1] 设G是一个非完全连通图，其坚韧度定义为

$t\left(G\right)=\min \left\{\left|S\right|/\omega \left(G-S\right):S\subseteq V\left(G\right),\omega \left(G-S\right)>1\right\}$。

如果 $t\left(G\right)=\left|S^{*}\right|/\omega \left(G-S^{*}\right)$，则称 $S^{*}$ 为G的一个坚韧集，简称t-集。

定义2 [1] 设G是一个图， $\omega \left(G\right)$ 为G的连通分支数。若对于G的任意点割集S，有 $\left|S\right|\ge t\omega \left(G-S\right)$，其中t是正实数，则称图G是t-坚韧的。

Chvátal同时研究了图的坚韧度和哈密尔顿性的关系，提出了一个关于坚韧度的著名猜想：存在一个确定的正数 $t_0$，任何 $t_0$ -坚韧图都是哈密尔顿图 [1]。2006年，Bauer在文献 [2] 中综述了坚韧度和周长的关系、2-坚韧猜想的反证明、因子、特殊图类、计算复杂度，以及与坚韧度相关的各种结果。

Broersm于1999年首次提出极小t-坚韧图的概念 [3]。

定义3 [3] 若图G的坚韧度，且每一个支撑真子图H的坚韧度 $t\left(H\right)<t$，则称G是极小t-坚韧的。

换言之，删除G中任意一条边e，图G的坚韧度减小，就说这个图G是极小t-坚韧的。

Katona给出了一些极小t-坚韧图顶点度的上界，并证明了每个极小1-坚韧图的无爪图是一个圈 [4]。2018年，Katona等构造出几类特殊的极小t-坚韧图，并证明了，对于任意正整数t以及任意正有理数 $t\le 1/2$，极小t-坚韧图的判定问题是DP-完备的 [5] [6]。

极小t-坚韧图具有重要的结构特性与研究意义，然而目前得到的极小t-坚韧图研究成果并不多。因此本文对极小t-坚韧图进行了研究，主要研究了几类笛卡尔积图和线图的极小t-坚韧性，并构造了一类k-正则的极小k/2-坚韧图。文中提及的图均为简单无向图，未加说明的概念和术语见文献 [7]。

2. 几类特殊的极小t-坚韧图

2.1. 笛卡尔积图的极小t-坚韧性

本节主要研究几类常见的笛卡儿积图，证明了完全图与完全图，路与圈的笛卡儿积图是极小t-坚韧的。

定义4设 $G_1$ 和 $G_2$ 是两个点不交的简单图， $G_1$ 和 $G_2$ 的笛卡尔积 $G_1\times G_2$ 是一个简单图，其中 $V\left(G_1\times G_2\right)=V\left(G_1\right)\times V\left(G_2\right)$，并且对 $u_1,v_1\in V\left(G_1\right)$， $u_2,v_2\in V\left(G_2\right)$， $\left(\left(u_1,u_2\right),\left(v_1,v_2\right)\right)\in E\left(G_1\times G_2\right)$ $\iff$ $u_1=v_1$，且 $\left(u_2,v_2\right)\in E\left(G_2\right)$ 或者 $u_{\text{2}}=v_{\text{2}}$ 且 $\left(u_{\text{1}},v_{\text{1}}\right)\in E\left(G_{\text{1}}\right)$。

引理1 [8] 设 $K_m\times K_n\left(m,n\ge 2\right)$ 是两个完全图的笛卡尔积，则 $t\left(K_m\times K_n\right)=\frac{m+n}{2}-1$。

引理2 [9] 设，其中 $m,n\ge 3$，则

1) G是 $\left(m+n-2\right)$ -正则的；

2) G是 $\left(m+n-2\right)$ -连通的。

定理1设 $K_m,K_n\left(m,n\ge 3\right)$ 是两个完全图，则 $K_m\times K_n$ 是极小 $\left(\frac{m+n}{2}-1\right)$ -坚韧的。

证明由引理1知， $t\left(K_m\times K_n\right)=\frac{m+n}{2}-1$。再由引理2，容易知道，对 $K_m\times K_n$ 的任意一点 $N\left(w\right)$ w，其邻点集即为 $K_m\times K_n$ 的一个t-集，且 $\left|N\left(w\right)\right|=d\left(w\right)=m+n-2$， $w\left(K_m\times K_n-N\left(w\right)\right)=2$。设 $e=\left(u,v\right)$ 是 $K_m\times K_n$ 的任意一条边，记，则有 $d_H\left(u\right)=d_H\left(v\right)=m+n-3$。令S为u在H中的邻点集，则有 $\left|S\right|=m+n-3$， $\omega \left(H-S\right)=2$。

这表明

$t\left(H\right)\le \frac{\left|S\right|}{\omega \left(H-S\right)}=\frac{m+m-3}{2}<t\left(K_m\times K_n\right)$

由定义3即得， $K_m\times K_n$ 是极小 $\left(\frac{m+n}{2}-1\right)$ -坚韧的。

定理2设 $P_2$， $C_m\left(m\ge 3\right)$ 分别表示路和圈，其中m为奇数，则 $P_2\times C_m$ 是极小 $\frac{m}{m-1}$ -坚韧的。

证明明显地， $P_2\times C_m$ 是3-正则图。设 $V\left(P_2\right)=\left\{1,2\right\}$， $V\left(C_m\right)=\left\{1,2,\cdots ,m\right\}$，且在 $C_m$ 中，点i的邻点是 $i-1$ 和 $i+1$，其中 $i=1,2,\cdots ,m$，并且关于模m同余。记 $V\left(P_2\times C_m\right)=\left\{11,12,\cdots ,1m;21,22,\cdots ,2m\right\}$，则由

坚韧度的定义，易知 $\left\{11,13,\cdots ,1m;22,24,\cdots ,2\left(m-1\right)\right\}$ 是 $P_2\times C_m$ 的一个t-集， $t\left(P_2\times C_m\right)=\frac{m-1}{m}$。设 $e=\left(u,v\right)$ 是 $P_2\times C_m$ 的任意一条边，则在中， $u,v$ 均为2度点。因为 $\left|N\left(u\right)\right|=2$， $\omega \left(P_2\times C_m-e-N\left(u\right)\right)=2$，所以有 $t\left(P_2\times C_m-e\right)\le 1<t\left(P_2\times C_m\right)$。故结论成立。

当 $n>2$ 或m为偶数时， $t\left(P_n\times C_m-e\right)\le t\left(P_n\times C_m\right)$，所以 $P_n\times C_m$ 不一定是极小t-坚韧图。

2.2. 轮形图的极小t-坚韧性

定义5设和 $G_2$ 是两个点不交的图， $G_1$ 和 $G_2$ 的联图，记为，是指在 $G_1\cup G_2$ 中将 $G_1$ 的每个顶点与 $G_2$ 的每个顶点之间用一条边连接起来所得到的图。

定义6称 $K_{\text{1}}$ 和 $C_n$ 的联图 $K_1\vee C_n$ 为轮形图，记为 $W_{1,n}$。 $K_{\text{1}}$ 中的点称为 $W_{1,n}$ 的中心，与该点关联的边称为辐条。

定理3轮形图 $W_{1,n}\left(n\ge 4\right)$ 是极小3/2-坚韧的。

证明由轮形图的结构易知，其中心和 $C_n$ 上任意两个不相邻的点构成一个t-集，故有

$t\left(W_{1,n-1}\right)=3/2$。

对于任意的 $e\in E\left(W_{1,n}\right)$，考虑以下两种情形。

情形1 $e\in C_n$。设 $e=\left(u,v\right)$，则在 $W_{1,n-1}-e$ 中, $u,v$ 均为2度点。因为 $\omega \left(W_{1,n}-e-N\left(u\right)\right)=2$，所以 $t\left(W_{1,n}-e\right)\le 1<t\left(W_{1,n}\right)$。

情形2 $e\notin C_n$。用v表示e在圈 $C_n$ 上的任一端点，v为2度点。与情形1同理，可知 $t\left(W_{1,n}-e\right)\le 1<t\left(W_{1,n}\right)$。

综上所述，结论成立。

2.3. 线图的极小t-坚韧性

本节主要讨论三类线图的极小t-坚韧性，证明了路，圈，完全二部图的线图是极小t-坚韧的。

定义7一个图G的线图用 $L\left(G\right)$ 来表示，它的顶点集是G的边集， $L\left(G\right)$ 中任意两点之间是相邻的，当且仅当G中对应的边是相邻的。

引理3 [5] 树T是极小 $\frac{\text{1}}{\Delta \left(T\right)}$ -坚韧的弦图。

定理4设 $P_n\left(n\ge 3\right)$ 是n阶路，则其线图 $L\left(P_n\right)$ 是极小1/2-坚韧的。

证明由线图的定义， $L\left(P_n\right)$ 是 $n-1$ 阶的路。由引理3， $P_n\left(n\ge 3\right)$ 是极小1/2-坚韧的。

定理5设 $C_n\left(n\ge 3\right)$ 是n阶圈，则其线图 $L\left(C_n\right)$ 是极小1-坚韧的。

证明由圈的结构和坚韧度的定义易知，n阶圈 $C_n$ 是极小1-坚韧的。又因为 $L\left(C_n\right)=C_n$，所以 $L\left(C_n\right)$ 是极小1-坚韧的。

完全二部分图的线图 $L\left(K_{m,n}\right)$ 是两个完全图的笛卡尔积，因此有如下结论：

定理6设 $K_{m,n}\left(m\ge \text{1},n\ge 2\right)$ 是完全二部分图，则其线图 $L\left(K_{m,n}\right)$ 是极小 $\left(\frac{m+n}{2}-1\right)$ -坚韧的。

3. 一类极小t-坚韧正则图的构造

本节以轮形图为基础，构造了一类阶的k-正则的极小k/2-坚韧图。

定义8设 $W_{1,k}\left(k\in Z_{+}\right)$ 是轮形图，将中心点之外的每个顶点都用一个k阶团替换，记这些团为 $C_1,C_2,\cdots ,C_k$，任意两个团 $C_i$ 和 $C_j$ 之间恰有一条边相连，每个团中的每个顶点有且仅有一个邻点不在这个团中。将所得到的图记为 $H_k$，则 $H_k$ 是 $k^2+1$ 阶的k-正则图。图1给出的是一个例子 $H_5$。

Figure 1. A 5-regular graph $H_{\text{5}}$ with order 26

图1. 一个26阶的5-正则图 $H_{\text{5}}$

定理7由定义8所构造的图 $H_k$ 是 $k^2+1$ 阶k-正则的极小k/2-坚韧图，其中 $k\in Z_{+}$。

证明因为 $H_k$ 是 $k^2+1$ 阶k-正则图，则对 $H_k$ 的任意一点u，其邻点集 $N\left(u\right)$ 为 $H_k$ 的一个t-集，且 $\left|N\left(u\right)\right|=d\left(u\right)=k$， $\omega \left(H_k-N\left(u\right)\right)=2$，即 $t\left(H_k\right)=k/2$。设 $e=\left(u,v\right)$ 是 $H_k$ 的任意一条边，则在 $H_k-e$ 中， $d\left(u\right)=d\left(v\right)=k-1$。令S为u在 $H_k-e$ 中的邻点集，则 $\left|S\right|=k-1$， $\omega \left(\left(H_k-e\right)-S\right)=2$。易知S是 $H_k-e$ 的一个t-集，从而

$t\left(H_k-e\right)=\frac{k-1}{2}<t\left(H_k\right)$。

所以， $H_k$ 是极小k/2-坚韧的。

4. 总结

坚韧度是用来刻画网络抗毁性的一个重要参数。坚韧度与图的结构、哈密尔顿性结合的研究一直是图论中的热点问题。本文证明了几类笛卡尔积图和线图是极小t-坚韧的，并且构造出一类k-正则的极小k/2-坚韧图。极小t-坚韧图是大量存在的，但是找到这些图比较困难。有关极小t-坚韧图的构造与分类，仍有很多问题值得深入研究。