星图的R¹-限制性点割

The R¹-Restricted Cuts of Star Graphs

摘要: 互联网络的拓扑结构可以用图论模型来描述，因此图论在研究网络问题时扮演着重要角色。连通度是衡量一个网络容错性和可靠性的重要指标。然而，在实际情况中，网络中一个点的所有邻点同时发生故障的概率较小，因此经典连通度在一定程度上低估了互联网络的容错性。为了更准确地评估网络的连通性，引入了条件连通度的概念，并进一步提出了R^k-连通度的概念，使得连通度问题更具有现实意义。本文主要研究并刻画了星图的全部基数最小的R¹-限制性点割。

Abstract: The topology of the Internet can be described using graph theory models, thus graph theory plays an important role in studying network issues. Connectivity is a crucial metric for assessing the fault tolerance and reliability of a network. However, in practical scenarios, the probability of all neighbors of a node in the network failing simultaneously is very small. Therefore, classic connectivity to some extent underestimates the fault tolerance of the Internet. To more accurately evaluate network connectivity, the concept of conditional connectivity has been introduced, and further, the concept of R^k-connectivity has been proposed, making the connectivity problem more practically significant. This paper primarily studies and characterizes the minimum cardinality R¹-restricted cut of star graphs.

1. 引言

设G是一个简单连通图且 $S\subseteq V\left(G\right)$ ，若 $G-S$ 不连通，则S是G的点割；G中含点数最少的点割称为G的最小点割，G的最小点割的基数用 $\kappa \left(G\right)$ 表示，称为G的连通度 [1] 。但是，一个点的所有邻点很少同时发生故障，于是，Harary [2] 引入了条件连通度，之后，Esfahanian [3] 又提出了R^k-连通度的概念。设G是一个简单连通图且 $S\subseteq V\left(G\right)$ 。若对 $V\left(G\right)-S$ 中的任意一个点u，其在 $G-S$ 中至少有k个邻点，则S称为G的R^k-点集；若对G的一个R^k-点集S， $G-S$ 不连通，则称S是G的R^k-点割；G中含点数最少的R^k-点割称为G的最小R^k-点割；G中最小的R^k-点割的基数 ${\kappa }^k\left(G\right)$ 称为G的R^k-连通度。

基于图最小的R^k-点割的刻画，文献 [4] 提出了超R^k连通的概念。若对于G中每一个最小R^k-点割S， $G-S$ 都包含一个同构于某一确定图H的分支，其中H与图G和整数k有关，则称图G是超R^k连通的。换言之，若G超R^k-连通，则G中每一个最小R^k-点割S都是某一确定图H在G中的邻点所构成的集合。

包含n个元 $\left\{1,2,\cdots ,n\right\}$ 的全体置换构成的群叫做n次对称群，表示为 $Sym\left(n\right)$ 。令 $\Gamma$ 为 $Sym\left(n\right)$ 中一些对换所构成的集合，称 $G\left(\Gamma \right)$ 为 $Cay\left(Sym\left(n\right),\Gamma \right)$ 的对换生成图，其点集为 $\left\{1,2,\cdots ,n\right\}$ ，i与j在 $G\left(\Gamma \right)$ 中相邻当且仅当对换 $\left(ij\right)\in \Gamma$ 。若 $G\left(\Gamma \right)$ 为一颗星，则其生成的Cayley图 $Cay\left(Sym\left(n\right),\Gamma \right)$ 记作S_n，亦即： $S_n=Cay\left(Sym\left(n\right),\Gamma \right)=Cay\left(Sym\left(n\right),\left\{\left(12\right),\left(13\right),\cdots ,\left(1n\right)\right\}\right)$ 。

一些具有优良性质的Cayley图的限制性点连通度吸引了学者们的关注 [5] [6] [7] [8] [9] 。本文将研究并刻画了星图的全部基数最小的R¹-限制性点割，并证明了星图是超R¹连通的。

2. 引理

为了证明主要结果，我们介绍以下引理：

引理2.1 [10] 令 $G\left(\Gamma \right)$ 是凯莱图 $G=Cay\left(Sym\left(n\right),\Gamma \right)$ 的对换生成图，其中 $n\ge 3$ 且 $\left|E\left(G\left(\Gamma \right)\right)\right|=m$ 。设 $S\subseteq V\left(G\right)$ ，则以下结论成立：

1) 图G不含有子图 $K_{2,4}$ ；

2) 如果 $G\left(\Gamma \right)$ 不含有三角形，则图G不含有子图 $K_{2,3}$ ；

3) $G\left(\Gamma \right)\kappa \left(G\right)=m$ ；

4) G是m-正则的二部图。

定理2.2 [10] 设G是由具有m条边n个顶点的生成图A生成的Cayley图，其中 $m\ge 7$ 。假设T是G中的一个点集，满足如果A没有三角形， 则 $\left|T\right|\le m+2$ ；如果A具有三角形，则 $\left|T\right|\le 2m-3$ 。以下之一成立：

1) $G-T$ 连通。

2) $G-T$ 不连通，且其恰有两个分支，其中之一为孤立点。

3) 生成图A没有三角形， $G-T$ 不连通，且其恰有两个分支，其中之一为 $K_2$ ，且 $\left|T\right|\le 2m-2$ 。

4) 生成图A没有三角形， $G-T$ 不连通，且其恰有三个分支，其中有两个为孤立点，且 $\left|T\right|\le 2m-2$ 。

5) 生成图A有三角形， $G-T$ 不连通，且其恰有三个分支，其中有两个为孤立点，且 $\left|T\right|\le 2m-3$ 。

由于的对换生成图是一颗星，星中不含有三角形。于是，我们有以下推论：

推论2.3 设 $n>5$ ，假设F是S_n的一个点集，且满足 $\left|F\right|\le 2\left(n-1\right)-2$ ，那么以下之一成立：

1) $G-T$ 连通。

2) $G-T$ 不连通，且其恰有两个分支，其中之一为孤立点。

3) $G-T$ 不连通，且其恰有两个分支，其中之一为K₂，且 $\left|F\right|=2\left(n-1\right)-2$ 。

4) $G-T$ 不连通，且其恰有三个分支，其中有两个为孤立点，且 $\left|F\right|=2\left(n-1\right)-2$ 。

推论2.4 S_n中没有子图 $K_{2,3}$ 和 $K_{2,4}$ 。

S_n中的两个点u和v相邻当且仅当在S中存在 $\left(1i\right)$ 使得 $v=u\left(1i\right)$ 。也就是 $u=\left(p_1,\cdots ,p_i,\cdots ,p_n\right)$ ，则 $v=\left(p_i,\cdots ,p_1,\cdots ,p_n\right)$ ，反之亦然。记 $S_{n-1}^i$ 是S_n的 $\left(n-1\right)$ -维子星 $\left(i\in \left\{2,\cdots ,n\right\}\right)$ ，它是由点集 $\left\{\left(p_1,p_2,\cdots ,p_{n-1},i\right)|\left(p_1,\cdots ,p_{n-1}\right)是\left\{1,\cdots ,n\right\}\backslash \left\{i\right\}的所有置换\right\}$ 所导出的子图。显然 $S_{n-1}^i$ 是一个 $\left(n-1\right)$ -维子星， $V\left(S_{n-1}^i\right)$ 是最后一个位置固定为i，前 $\left(n-1\right)$ 个位置是 $\left\{1,\cdots ,i-1,i+1,\cdots ,n\right\}$ 这 $\left(n-1\right)$ 个数的所有排列。由上面的讨论可知：S可以分解成n个 $\left(n-1\right)$ -维子星 $S_{n-1}$ ，它们分别是 $S_{n-1}^1,S_{n-1}^2,S_{n-1}^3,\cdots ,S_{n-1}^n$ 。对于 $u\in V\left(S_{n-1}^i\right)$ ， $N\left(u\right)\cap V\left(S_{n-1}^i\right)=\left\{\left(12\right)u,\cdots ,\left(1n-1\right)u\right\}$ ，而有唯一的邻点 $u\text{'}=\left(1n\right)u$ 落在 $V\left(S_n-S_{n-1}^i\right)$ 内，把这样的邻点称为u的外邻点。令 $\left[i,j\right]=\left\{t:i\le t\le j\right\}$ ，其中 $i<j$ 。 $S\left[i,j\right]$ 表示点集 $\left\{u:u\in V\left(S_{n-1}^t\right),t\in \left[i,j\right]\right\}$ 在S_n中的导出子图。容易验证，对于任意的 $i\in \left[2,n\right]$ ， $S_{n-1}^i$ 的任意一点u均在 $S_n-S_{n-1}^i$ 中有唯一邻点 $u\text{'}=\left(1n\right)u$ ，即为u的外邻点。

引理2.5 [11] $N\left(S_{n-1}^j\right)\left(j=1,\cdots ,n\right)$ 是一个基数为 $\left(n-1\right)!$ 的独立集，并且 $\left|N\left(S_{n-1}^j\right)\cap N\left(S_{n-1}^k\right)\right|=\left(n-2\right)!\left(k\ne j\right)$ 。

设 $N_{S_n}^{out}\left(u\right)$ （简记为 $N^{out}\left(u\right)=N_{S_n}\left(u\right)\backslash N_{S_{n-1}^i}\left(u\right)$ ）中 $u\in V\left(S_{n-1}^i\right)$ ，即 $N_{S_n}^{out}\left(u\right)$ 为u在S_n中但不在 $S_{n-1}^i$ 中的邻点。则对任意的点集 $M\subseteq V\left(S_{n-1}^i\right)$ ，令 $N_{S_n}^{out}\left(M\right)$ (另标记为 $N^{out}\left(M\right)=\left\{N_{S_n}^{out}\left(u\right)|u\in M\right\}$ )，于是可证明以下的引理成立。

引理2.6 设 $F\subseteq V\left(S_n\right)$ ，对任意的 $p\in \left[i,l\right]$ ，记 $F_p=F\cap V\left(S_{n-1}^p\right)$ ，如果以下条件同时成立：

1) 对任意的 $t\in \left[j,j-1\right]$ ，令 $H_t$ 是 $S_{n-1}^t-F_t$ 的一个分支，且 $H_t$ 与 $S\left[j,l\right]-F$ 间存在边相连；

2) 对任意的 $q\in \left[j,l\right]$ ， $S_{n-1}^q-F_q$ 均是连通的；

3) 对任意的 $s\in \left[j,l-1\right]$ ， $S_{n-1}^s-F_s$ 与 $S_{n-1}^{s+1}-F_{s+1}$ 之间存在边相连；

则点集 $\left\{{\cup }_{t=i}^{j-1}V\left(H_t\right)\right\}\cup V\left(S\left[j,l\right]-F\right)$ 在S_n中的导出子图是连通的。

3. 主要结论的证明

定理3.1 [12] $\kappa \left(S_n\right)=n-1$ 且S_n是超连通的。

定理3.2 [13] ${\kappa }^1\left(S_n\right)=2n-4$ 。

引理3.3 S₄是超R¹连通的。

证明：设F是S₄的一个最小R¹-点割。由定理3.2，可知 $\left|F\right|=4$ 。对任意的 $i\in \left[1,4\right]$ ，记 $F_i=F\cap V\left(S_3^i\right)$ 。

断言： $0\le \left|J\right|\le 2$ ，其中 $J=\left\{i|S_3^i-F_i是不连通的\right\}$ 。

情形1： $\left|J\right|=0$ 。

对任意的 $i\in \left[1,n\right]$ ， $S_n^i-F_i$ 都是连通的。如果对任意 $i\in \left[1,3\right]$ 存在一条连接 $S_{n-1}^i-F_i$ 与 $S_{n-1}^{i+1}-F_{i+1}$ 的边，由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的。所以不妨假设没有连接 $S_3^1-F_1$ 与 $S_3^2-F_2$ 的边。因此 $\left|F_1\right|+\left|F_2\right|\ge 2$ 。不妨假设 $\left|F_1\right|\ge \left|F_2\right|$ ，从而 $\left|F_1\right|\ge 1$ ， $\left|F_2\right|\le 2$ ， $\left|F_3\cup F_4\right|\le 2$ 。由引理2.6，可知 $S\left[2,4\right]-F$ 是连通的。因为 $S_4-F$ 不连通且不含有孤立点，所以 $S_4-F$ 的某个非孤立点分支H的顶点集包含在 $V\left(S_3^1\right)-F_1$ 。显然， $2\le \left|V\left(H\right)\right|\le \left|V\left(S_3^1\right)-F_1\right|\le 5$ 。如果 $\left|V\left(H\right)\right|=2$ ，那么H是一条边且 $F=N\left(H\right)$ 。如果 $\left|V\left(H\right)\right|=3$ ，那么 $1\le \left|F_1\right|\le 3$ 。由引理2.5，可知存在一条连接 $S_3^1-F_1$ 与 $S_3^3-F_3$ 或者 $S_3^4-F_4$ 的边。注意到 $S\left[2,4\right]-F$ 是连通的，所以 $S_4-F=S\left[1,4\right]-F$ 是连通的，与F是S₄的点割相互矛盾。如果 $\left|V\left(H\right)\right|=4$ ，那么 $1\le \left|F_1\right|\le 2$ 。由引理2.5，可知存在一条连接 $S_3^1-F_1$ 与 $S_3^3-F_3$ 或者 $S_3^4-F_4$ 的边。注意到 $S\left[2,4\right]-F$ 是连通的，所以 $S_4-F=S\left[1,4\right]-F$ 是连通的，与F是S₄的点割相互矛盾。如果 $\left|V\left(H\right)\right|=5$ ，那么 $\left|F_1\right|=1$ ， $\left|F_2\right|=1$ 。 $\left|F_1\right|+\left|F_3\cup F_4\right|=3$ 可知存在一条连接 $S_3^1-F_1$ 与 $S_3^3-F_3$ 或者 $S_3^4-F_4$ 的边。注意到 $S\left[2,4\right]-F$ 是连通的，所以 $S_4-F=S\left[1,4\right]-F$ 是连通的，与F是S₄的点割相互矛盾。

情形2： $\left|J\right|=1$ 。

不妨设 $S_3^1-F_1$ 不连通，即 $\left|F_1\right|\ge 2$ 。不妨假设 $\left|F_2\right|\ge \left|F_3\right|\ge \left|F_4\right|$ 。因为 $\left|F\right|=4$ ，所以 $\left|F_2\right|\le 2$ 。

情形2.1： $\left|F_1\right|=2$ 。

由引理2.6，可知 $S\left[2,4\right]-F$ 是连通的。因为 $S_4-F$ 不连通且不含有孤立点，所以 $S_4-F$ 的某个非孤立点分支H的顶点集包含在 $V\left(S_3^1\right)-F_1$ 。因为 $\left|V\left(H\right)\right|\ge 2$ ， $\left|F_1\right|=2$ 且 $S_3^1-F_1$ 不连通，由推论2.3，可知 $S_3^1-F_1$ 恰有两个分支，其中之一为孤立点或者其恰有两个分支，其中之一为K₂，或者其恰有三个分支，其中有两个为孤立点。于是 $S_3^1-F_1$ 可能的分支情况为： $\left\{u_1\right\},H_1$ 或者 $K_2,H_1$ 。考虑 $S_3^1-F_1$ 分支情况为： $\left\{u_1\right\}$ ，H₁。因为 $S_4-F$ 不连通且不含有孤立点，所以存在一条连接 $\left\{u_1\right\}$ 和 $S\left[2,4\right]-F$ 的边。由引理2.5，可知存在一条连接H₁和 $S\left[2,4\right]-F$ 的边。又 $S\left[2,4\right]-F$ 是连通的，由引理2.6，可知 $S_4-F=S\left[1,4\right]-F$ 是连通的，与F是S₄的点割相互矛盾。考虑 $S_3^1-F_1$ 分支情况为：K₂，H₁。由引理2.5，可知存在一条连接H₁和 $S\left[2,4\right]-F$ 的边。设 $K_2=\left(x_1,y_1\right)$ 。设 $x_1,y_1$ 在 $S_4-S_3^1$ 的邻点为 $x_i,y_j,i\ne j$ 。若 $x_i\notin F$ 或者 $y_j\notin F$ ，则存在一条连接K₂和 $S\left[2,4\right]-F$ 的边。由引理2.6，可知 $S_4-F$ 是连通的，与F是S₄的点割相互矛盾。若 $x_i\in F$ 且 $y_j\in F$ ，则 $F=N\left(\left\{x_1,y_1\right\}\right)$ 。

情形2.2： $3\le \left|F_1\right|\le 4$ 。

此时， $\left|F_2\right|=1$ 。由引理2.6，可知 $S\left[2,4\right]-F$ 是连通的。因为 $S_4-F$ 不含有孤立点，由引理2.5，可知 $S_3^1-F_1$ 的所有分支均存在一条边与 $S\left[2,4\right]-F$ 相连。由引理2.6，可知 $S_4-F=S\left[1,4\right]-F$ 是连通的，与F是S₄的点割相互矛盾。

情形3： $\left|J\right|=2$ 。

不妨设 $S_3^1-F_1$ 和 $S_3^2-F_2$ 不连通。显然 $\left|F_1\right|=\left|F_2\right|=2$ ， $\left|F_3\right|=\left|F_4\right|=0$ 。由推论2.3，可知 $S_3^1-F_1$ 和 $S_3^2-F_2$ 均含有一个孤立点和一条边，记为 $u_1,K_2$ 和 $x_2,{K^{\prime }}_2$ 。

情形3.1：u₁和x₂相邻。

若 $F=N\left(\left\{u_1,x_2\right\}\right)$ ，则 $\left(u_1,x_2\right)$ 与为 $K_2,{K^{\prime }}_2$ 和以及 $S\left[3,4\right]-F$ 没有边相连，则 $S_4-F$ 不连通。

情形3.2：u₁和x₂不相邻。

由引理2.6，可知 $S\left[3,4\right]-F$ 是连通的。因为 $S_4-F$ 不连通且不含有孤立点，所以则 $u_1,x_2$ 与 $S\left[3,4\right]-F$ 间存在边相连 $S_4-F$ 。由引理2.5，可知 $K_2,{K^{\prime }}_2$ 和 $S\left[3,4\right]-F$ 间存在边相连。由引理2.6，可知 $S_4-F=S\left[1,4\right]-F$ 是连通的，与F是S₄的点割相互矛盾。□

定理3.4 设 $n\ge 4$ ，则S_n是超R¹连通的。

证明：根据引理3.3，只需考虑 $n\ge 5$ 时的情形。设F是S_n的一个最小R¹-点割。由定理3.2，可知 $\left|F\right|=2n-4$ 。对任意的 $i\in \left[1,n\right]$ ，记 $F_i=F\cap V\left(S_{n-1}^i\right)$ 。我们将证明 $F=N\left(\left\{u,v\right\}\right)$ ，其中u和v是S_n中一条边的两个端点。

断言： $0\le \left|J\right|\le 2$ ，其中 $J=\left\{i|S_{n-1}^i-F_i是不连通的\right\}$ 。

当 $\left|J\right|\ge 3$ 时，由定理3.2，可知 $2n-4\ge 3\left(n-2\right)$ ，矛盾。所以 $\left|J\right|\le 2$ 。

情形1： $\left|J\right|=0$ 。

对任意的 $i\in \left[1,n\right]$ ， $S_n^i-F_i$ 都是连通的。如果对任意 $i\in \left[1,n\right]$ 存在一条连接 $S_{n-1}^i-F_i$ 与 $S_{n-1}^{i+1}-F_{i+1}$ 的边，由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的。所以不妨假设没有连接 $S_{n-1}^1-F_1$ 与 $S_{n-1}^2-F_2$ 的边。因此 $\left|F_1\right|+\left|F_2\right|\ge \left(n-2\right)!\ge 3\left(n-3\right)$ 。

情形1.1： $n\ge 6$ 。

$\left|F_1\right|+\left|F_2\right|\ge \left(n-2\right)!\ge 3\left(n-3\right)>2n-4$ ，则 $S\left[2,n\right]-F$ 是连通的。由引理2.5，可知存在一条连接 $S_{n-1}^1-F_1$ 与 $S\left[2,n\right]-F$ 的边，由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的。

情形1.2： $n=5$ 。

$\left|F_1\right|+\left|F_2\right|\ge \left(n-2\right)!=6$ 。根据定理3.2，可知 $\left|F\right|=6$ 。从而 $\left|F_1\right|+\left|F_2\right|=6$ 。不妨假设 $\left|F_1\right|\ge \left|F_2\right|$ ，从而 $\left|F_1\right|\ge 3$ ， $\left|F_2\right|\le 3$ ， $\left|F_3\cup F_4\cup F_5\right|=0$ 。

根据引理2.6，可知 $S_5-F=S\left[2,5\right]-F$ 是连通的。又 $3\le \left|F_1\right|\le 6$ ，所以 $18\le \left|V\left(S_{n-1}^1-F_1\right)\right|\le 21$ ，根据引理2.5，可知存在一条连接 $S_4^1-F_1$ 与 $S\left[2,5\right]-F$ 的边，由引理2.6，可知 $S_5-F=S\left[1,5\right]-F$ 是连通的。

情形2： $\left|J\right|=1$ 。

不妨设 $S_{n-1}^1-F_1$ 不连通。

情形2.1： $S_{n-1}^1-F_1$ 不含有孤立点。

F₁是 $S_{n-1}^1$ 的一个限制性点割，则 $2\left(n-1\right)-4=2n-6\le \left|F_1\right|\le 2n-4$ 。以下用数学归纳法证明 $S_n\left(n\ge 5\right)$ 是超连通的。 $n=4$ 时，由引理3.3，可知由S₄是超连通的。假设 $n\ge 5$ 时， $S_{n-1}$ 是超连通的。考虑以下情况。

情形2.1.1： $\left|F_1\right|=2n-6$ 。

因为 $S_{n-1}$ 是超连通的，F₁为其限制性R¹-点割，且 $\left|F_1\right|=2n-6$ ，则 $F=N\left(\left\{u,v\right\}\right)$ ，其中 $u~v$ 。于是不妨设 $S_{n-1}^1$ 的某个最小的限制性R¹-点割由顶点为 $u,v$ 的一条边的所有邻点所构成，则 $S_{n-1}^1-F_1$ 不连通且 $F_1=N_1\left(\left\{u,v\right\}\right)$ ，所以 $\left(u,v\right)$ 与H₁恰是 $S_{n-1}^1-F_1$ 的所有分支。又 $\left|J\right|=1$ ，则 $S_{n-1}^t-F_t,t\in \left[2,n\right]$ 均连通。 ${\displaystyle {\sum }_{i=2}^n\left|F_i\right|}=2$ ，所以 $S_{n-1}^i-F_i$ 与 $S_{n-1}^j-F_j\left(i,j\in \left\{2,3,\cdots ,n\right\}\right)$ 之间均有边相连，由引理2.6，可知 $S\left[2,n\right]-F$ 连通。 $V\left(H_1\right)=\left(n-1\right)\text{!}-\left(2n-6\right)-2\ge 4\left(n-2\right)-2n+4=2n-4\ge 6>2$ 。所以存在一条连接H₁和 $S\left[2,n\right]-F$ 的一条边。设 $u,v$ 在 $S_n-S_{n-1}^1$ 的邻点分别为 $u_i,v_j,i\ne j$ 且 $i,j\in \left\{2,3,\cdots ,n\right\}$ 。若 $u_i$ 或者 $v_j$ 属于 $S\left[2,n\right]-F$ ，则 $\left(u,v\right)$ 与 $S\left[2,n\right]-F$ 之间有边相连，由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾，故若 $u_i\in F$ 且 $v_j\in F$ 。此时点集 $V\left(H_1\right)\cup V\left(S\left[2,n\right]-F\right)$ 在 $S_n-F$ 的导出子图连通，又 $S_n-F$ 不连通且不含有孤立点，则 $\left(u,v\right)$ 为 $S_n-F$ 的一个非孤立点分支，即 $F=N\left(\left\{u,v\right\}\right)$ 。

情形2.1.2： $\left|F_1\right|=2n-5$ 。

${\displaystyle {\sum }_{i=2}^n\left|F_i\right|}=1$ ，由引理2.6，可知得 $S\left[2,n\right]-F$ 连通。令 ${F^{\prime }}_1=F_1\backslash \left\{x\right\}$ ，则 $\left|{F^{\prime }}_1\right|=2n-6$ 。

如果 $S_{n-1}^1-{F^{\prime }}_1$ 不连通。由推论2.3，可知 $S_{n-1}^1-{F^{\prime }}_1$ 恰有两个分支，其中之一为K₂。于是 $S_{n-1}^1-{F^{\prime }}_1$ 的分支情况为： $K_2,H_1$ 。此时 $K_2=\left(u,v\right)$ ， ${F^{\prime }}_1=N_1\left(\left\{u,v\right\}\right)$ 。若 $x\in K_2$ 。 $S_{n-1}^1-F_1$ 的分支情况为： $v,H_1$ 。 $S_n-F$ 不连通且不含有孤立点，所以v与 $S\left[2,n\right]-F$ 之间有边相连。 $V\left(H_1\right)=\left(n-1\right)\text{!}-\left(2n-5\right)-1\ge 2n-4\ge 6$ ，从而存在一条连接H₁与 $S\left[2,n\right]-F$ 的边。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾。若 $x\in H_1$ 。设 $u,v$ 在 $S_n-S_{n-1}^1$ 的邻点分别为 $u_i,v_j,i\ne j$ 且 $i,j\in \left\{2,3,\cdots ,n\right\}$ ，从而 $u_i$ 或者 $v_j$ 不属于 $S\left[2,n\right]-F$ ，即 $\left(u,v\right)$ 与 $S\left[2,n\right]-F$ 之间有边相连。 $\left|F_1\right|=2n-5$ ， $S_{n-1}^1$ 是 $\left(n-2\right)$ -正则的，所以 $S_{n-1}^1-F_1$ 最多有一个孤立点。 $V\left(H_1\right)=\left(n-1\right)\text{!}-\left(2n-6\right)-2\ge 2n-4\ge 6$ ，从而 $H_1-x$ 的所有分支均与 $S\left[2,n\right]-F$ 之间有边相连。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾。

如果 $S_{n-1}^1-{F^{\prime }}_1$ 连通。于是 $S_{n-1}^1-{F^{\prime }}_1$ 的分支情况为：H₁。显然， $x\in H_1$ 。 $\left|F_1\right|=2n-5$ ， $S_{n-1}^1$ 是 $\left(n-2\right)$ -正则的，所以 $S_{n-1}^1-F_1$ 最多有一个孤立点。如果 $S_{n-1}^1-F_1$ 有一个孤立点，设为t。 $S_n-F$ 不连通且不含有孤立点，所以x与 $S\left[2,n\right]-F$ 之间有边相连。 $S_{n-1}^1-F_1$ 除去t之外的所有分支的包含的点数是大于等于2的，又 ${\displaystyle {\sum }_{i=2}^n\left|F_i\right|}=1$ ，由引理2.5，可知这些分支均与 $S\left[2,n\right]-F$ 之间有边相连。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾。如果 $S_{n-1}^1-F_1$ 不含有孤立点。此时 $S_{n-1}^1-F_1$ 的所有分支的包含的点数是大于等于2的，又 ${\displaystyle {\sum }_{i=2}^n\left|F_i\right|}=1$ ，由引理2.5，可知这些分支均与 $S\left[2,n\right]-F$ 之间有边相连。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾。

情形2.1.3： $\left|F_1\right|=2n-4$ 。

${\displaystyle {\sum }_{i=2}^n\left|F_i\right|}=0$ ，由引理2.6，可知 $S\left[2,n\right]-F$ 连通。 $\left(n-2\right)!\ge 6>0$ ，由引理2.5，可知 $S_{n-1}^1-F_1$ 的所有分支均与 $S\left[2,n\right]-F$ 之间有边相连。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾。

情形2.2： $S_{n-1}^1-F_1$ 含有孤立点。

由定理3.1，可知 $\kappa \left(S_{n-1}\right)=n-2$ ，从而 $n-2\le \left|F_1\right|\le 2n-4$ 。考虑以下情况。

情形2.2.1： $\left|F_1\right|=n-2$ 。

${\displaystyle {\sum }_{i=2}^n\left|F_i\right|}=\left(2n-4\right)-\left(n-2\right)=n-2$ 。 $\left(n-2\right)!>n-2$ ，由引理2。6，可知 $S\left[2,n\right]-F$ 连通。由推论2。3，可知 $S_{n-1}^1-F_1$ 恰有两个分支，其中之一为孤立点，设为x。 $S_n-F$ 不连通且不含有孤立点，所以x与 $S\left[2,n\right]-F$ 之间有边相连。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾。

情形2.2.2： $n-1\le \left|F_1\right|\le 2n-4$ 。

$0\le {\displaystyle {\sum }_{i=2}^n\left|F_i\right|}\le n-3$ 。 $\left(n-2\right)\text{!}-\left(n-3\right)>3\left(n-3\right)-\left(n-3\right)=2\left(n-3\right)\ge 4$ 。由引理2.6，可知 $S\left[2,n\right]-F$ 连通。 $n-1\le \left|F_1\right|\le 2n-4$ ， $S_{n-1}^1$ 是 $\left(n-2\right)$ -正则的，所以 $S_{n-1}^1-F_1$ 最多有两个孤立点。由推论2.3，可知 $S_{n-1}^1-F_1$ 恰有两个分支，其中之一为孤立点，设为x。于是 $S_{n-1}^1-F_1$ 的分支情况为： $x,H_1$ 。 $S_n-F$ 不连通且不含有孤立点，所以x与 $S\left[2,n\right]-F$ 之间有边相连。 $V\left(H_1\right)-\left(n-3\right)-1\ge \left(n-1\right)\text{!}-\left(n-1\right)-\left(n-3\right)-1$ ，当 $n\ge 5$ 时， $V\left(H_1\right)-\left(n-3\right)-1\ge 6n-13\ge 17$ 。所以存在一条连接H₁和 $S\left[2,n\right]-F$ 的边。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，这F为S_n点割矛盾。

情形3： $\left|J\right|=2$ 。

不妨假设 $S_{n-1}^1-F_1$ 和 $S_{n-1}^2-F_2$ 不连通。又 $\left|F\right|=2n-4$ ，由定理3.1，可知 $\left|F_1\right|=\left|F_2\right|=n-2$ ， ${\displaystyle {\sum }_{i=2}^n\left|F_i\right|}=0$ 。由引理2.6，可知 $S\left[2,n\right]-F$ 连通。由推论2.3，可知 $S_{n-1}^1-F_1$ 恰有两个分支，其中之一为孤立点，设为 $u,v$ 。于是 $S_{n-1}^1-F_1$ 和 $S_{n-1}^2-F_2$ 的分支情况为： $u,H_1$ 和 $v,H_2$ 。考虑以下情形。

情形3.1：u和v相邻。

此时 $F=N\left(\left\{u,v\right\}\right)$ ，则 $\left(u,v\right)$ 与为 $H_1,H_2$ 和以及 $S\left[2,n\right]-F$ 没有边相连，则 $S_n-F$ 不连通且不含有孤立点， $\left(u,v\right)$ 为 $S_n-F$ 的一个非孤立点分支，即 $F=N\left(\left\{u,v\right\}\right)$ 。

情形3.2：u和v不相邻。

$S_n-F$ 不连通且不含有孤立点，所以 $u,v$ 与 $S\left[2,n\right]-F$ 之间均有边相连。由引理2.5，可知H₁和H₂中的某些点在 $S_n-\left(S_{n-1}^1\cup S_{n-1}^2\right)$ 中存在外邻点，即H₁和H₂与 $S\left[2,n\right]-F$ 之间均有边相连。由引理2.6，可知 $S_n-F=S\left[1,n\right]-F$ 是连通的，与F是S_n的点割相互矛盾。□

4. 结语

如今，随着科学技术的发展，一些具有良好性质的互联网络吸引了人们的关注。本文对星图的全部基数最小的R¹-限制性点割进行了研究。证明了当 $n\ge 4$ 时，星图S_n是超R¹连通的。这一结论将为对星图的容错性做出更加合理的评估。

致谢

本篇论文是在胡老师的耐心指导中下完成的。正是胡老师悉心指导和专业知识使我能够顺利完成这篇论文。此外，我要感谢我的家人和同学们，是你们的支持和帮助让我能够坚持到最后。

参考文献