圈的k阶幂图的连通性研究

Study on the Connectivity of the kth Power of Cycles

摘要: 设G是连通图，G的k阶幂图$G^k$ 与G的顶点集相同且$G^k$ 中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k，本文给出了圈的幂图$C_n^k$ 的点连通度$\kappa \left(C_n^k\right)$ ，边连通度$\lambda \left(C_n^k\right)$ 和限制边连通度${\lambda }_2\left(C_n^k\right)$ 。我们得到当$1\le k<\lfloor \frac{n}{2}\rfloor$ 时，$\kappa \left(C_n^k\right)=\lambda \left(C_n^k\right)=2k$ 。关于限制边连通度，当$n\ge 4$ 时，${\lambda }_2\left(C_n^k\right)=2\lambda \left(C_n^k\right)-2$ 。

Abstract: Let G be a connected graph. The kth power $G^k$ of G is a graph having the same vertex set of G such that the two vertices in $G^k$ are adjacent if and only if the distance between the two vertices in G is less than or equal to k. In this paper, the connectivity $\kappa \left(C_n^k\right)$ , edge connectivity $\lambda \left(C_n^k\right)$ and restricted edge connectivity ${\lambda }_2\left(C_n^k\right)$ of $C_n^k$ are studied. We obtain the following results: $\kappa \left(C_n^k\right)=\lambda \left(C_n^k\right)=2k$ when $1\le k<\lfloor \frac{n}{2}\rfloor$ ；${\lambda }_2\left(C_n^k\right)=2\lambda \left(C_n^k\right)-2$ when $n\ge 4$ .

1. 引言

幂图理论主要研究图的拓扑结构和图的动力学性质，尤其在社交网络分析、网络科学、计算机科学、社会学、化学等方面的应用发挥着重要作用。特别地，幂图理论可以通过识别出网络中的关键节点(如度数大的节点)来分析网络中的节点重要性、网络结构的稳定性以及信息传播的效率，这些节点对于信息传播和网络的连通性至关重要。在化学中，可以将原子作为节点，化学键作为边，用幂图理论来分析这些化学分子结构图，通过计算图的某些特征值去预测分子的性质和反应机制。图的幂图理论在不同领域的适用性较为广泛，随着对幂图的深入研究，它将在更多领域中成为我们研究的一个强大工具。连通性是图论中的一个基本概念，它反映了图中节点之间的连接程度，其在通讯网络中起着重要的作用，因为在这些网络中的连通性越好，网络可靠性就越高。对于幂图而言，其连通性的研究不仅有助于理解幂图本身的性质，还对相关应用领域具有重要的理论指导意义。关于幂图的连通性的研究，目前也已经有一定的结果。例如，关于树和圈的二次幂图的Hamilton连通性，圈的幂图s-迹连通性的结果可以参考文献[1] [2]，路的k阶幂图的连通性也有一定结果，其点连通度、边连通度和限制边连通度都已得出具体结论，详情可参考文献[3]。圈是一种特殊的图，其所有顶点构成一个闭合路径，研究圈的幂图的连通性，可以帮助我们理解在特定结构下幂图的性质变化。本文将研究圈的k阶幂图的连通性，包括其点连通度、边连通度以及限制边连通度。

若无特殊说明，本文提及的图均是无向有限简单连通图。关于图$G=\left(V,E\right)$ ，$V=V\left(G\right)$ 和$E=E\left(G\right)$ 分别表示其顶点集和边集，$n=n\left(G\right)=\left|V\left(G\right)\right|$ 和$m=m\left(G\right)=\left|E\left(G\right)\right|$ 分别表示其阶数和边数。在图G中点v的度定义为与点v相关联的边数，记为$d\left(v\right)=d_G\left(v\right)$ 。G的最小度即G中所有点的度的最小值，记为$\delta =\delta \left(G\right)$ 。若图G中所有点的度都为k，则称图G为k-正则图。对于n个顶点的图，若其所有顶点按某一循环顺序的方式排列后，可使得该序列中连续排列的两点在图中是相邻的，否则在图中不相邻，则该图称为圈，记为$C_n\left(n\ge 3\right)$ 。对于n个顶点的简单图，若其任意两点均相邻，则该图称为完全图，记为$K_n$ 。若对于任意顶点$u,v\in V\left(G\right)$ ，都存在G的一个自同构映射将u映射到v，则图G称为点可迁图。设G为连通图，若有$V_1\subseteq V\left(G\right)$ ，使得图G删除$V_1$ 后得到的子图是不连通的，则称$V_1$ 是G的一个点割集；若有$E_1\subseteq E\left(G\right)$ ，使得图G删除$E_1$ 后得到的子图是不连通的，则称$E_1$ 是G的一个边割集。图G的点连通度$\kappa \left(G\right)$ 是G的最小点割集中所含顶点的数目，即：$\kappa \left(G\right)=\min \left\{\left|V_1\right|:V_1为G的点割集\right\}$ 。图G的边连通度$\lambda \left(G\right)$ 是G的最小边割集中所含边的数目，即：$\lambda \left(G\right)=\min \left\{\left|E_1\right|:E_1为G的边割集\right\}$ 。在图$G=\left(V,E\right)$ 中，假设X和Y是V的子集，连接X和Y的边集记为$E\left[X,Y\right]$ 。若$X=V\backslash Y$ ，称$E\left[X,Y\right]$ 是X在G中的伴随边割，记为$\partial \left(X\right)$ ，且$\partial \left(X\right)=\partial \left(Y\right)$ 。以V的子集X为顶点集，E中两个顶点均属于X的边为边集形成的子图称为G的由X导出的子图，简称导出子图，记为$G\left[X\right]$ 。

限制边连通度是图论中一个重要的概念，它可以用于衡量网络的可靠性和容错性。在网络科学和计算机科学中，限制边连通度有助于设计和分析网络的拓扑结构，以确保网络在面对节点或边的故障时仍能保持良好的连通性。Esfahanian和Hakimi [4]给出了图的限制边割和限制边连通度的定义。对于G的一个边割集S，若$G\backslash S$ 不含孤立点，则S称为限制边割。图G的限制边连通度${\lambda }_{\text{2}}\left(G\right)$ 是G的最小限制边割所含边的数目。其中文献[4]还给出了限制边连通度的上界${\lambda }_{\text{2}}\left(G\right)\le {\xi }_2\left(G\right)$ ，其中${\xi }_{\text{2}}\left(G\right)=\min \left\{d\left(u\right)+d\left(v\right)-2:uv\in E\left(G\right)\right\}$ 是图G的最小边度，当等号成立时，图G称为极大限制边连通的或${\lambda }_2$ 最优的。关于图G是极大限制边连通的充分条件可参考文献[5]-[8]。对于未说明的其他符号和术语，请读者参考文献[9]。

2. 预备知识

设G是连通图，G的k阶幂图$G^k$ 与G的顶点集相同且$G^k$ 中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k，也简称为G的幂图[10]。在“图1”和“图2”中，我们给出了圈的幂图$C_{\text{6}}^k$ 的示意图($k=1,2,3$ )和$C_{\text{10}}^k$ 的示意图($k=1~5$ )。在后文中，我们将$C_n$ 的顶点按循环性顺序排列并记为$v_1{v}_2\cdot \cdot \cdot v_i{v}_{i+1}\cdot \cdot \cdot v_n{v}_1$ ，即在圈$C_n$ 上$v_i$ 和$v_j$ 相邻当且仅当$\left|i-j\right|=1$ 。

Figure 1. The kth power graph of $C_6$

图1. $C_6$ 的k阶幂图

Figure 2. The kth power graph of $C_{\text{10}}$

图2. $C_{\text{10}}$ 的k阶幂图

对于本文所讨论的圈$C_n$ 的幂图，规定$n\ge 3$ 。

引理2.1：当$k\ge \lfloor \frac{n}{2}\rfloor$ 时，$C_n^k$ 为完全图，也为$\left(n-1\right)$ -正则图。

证明：某两点u和v之间的距离规定为它们之间最短路径的长度。圈$C_n$ 上每个点到其它所有点的距离均小于等于$\lfloor \frac{n}{2}\rfloor$ ，即小于等于k，因此，当$k\ge \lfloor \frac{n}{2}\rfloor$ 时，$C_n^k$ 为完全图。此时$C_n^k$ 每个点的度都等于$n-1$ ，为$\left(n-1\right)$ -正则图。□

引理2.2：当$1\le k<\lfloor \frac{n}{2}\rfloor$ 时，$C_n^k$ 为2k-正则图。

证明：在圈$C_n$ 中，对于任意的点u，距离为1的点有2个(即u的邻点)，距离为2的点有2个(u的两邻点各有一个与u不同的邻点)，以此类推，距离为$1\le d<\lfloor \frac{n}{2}\rfloor$ 的点有2个，则当$1\le k<\lfloor \frac{n}{2}\rfloor$ 时，$C_n^k$ 中每个点的邻点数为2k，因此$C_n^k$ 为2k-正则图。□

引理2.3：$C_n^k$ 是点可迁图。□

引理2.4 ([4]惠特尼不等式)：对于任意的图G，均有：$\kappa \left(G\right)\le \lambda \left(G\right)\le \delta \left(G\right)$ 。□

引理2.5 [4]：设图G是简单的连通点可迁图，度d是正整数，则边连通度$\lambda \left(G\right)=d$ 。□

引理2.6 [11]：设图G是有限图，k是正整数。则$\kappa \left(G^k\right)\ge \min \left(\left|V\left(G\right)\right|-1,k\kappa \left(G\right)\right)$ 。□

3. $C_n^k$ 的点连通度，边连通度与限制边连通度

引理3.1：当$1\le k<\lfloor \frac{n}{2}\rfloor$ 时，图$C_n^k$ 的点连通度等于2k，即$\kappa \left(C_n^k\right)=2k$ 。

证明：图$C_n$ 的点连通度$\kappa \left(C_n\right)=2$ 。又由$1\le k<\lfloor \frac{n}{2}\rfloor$ 知$n\ge 2k+1$ ，则$\min \left(\left|V\left(C_n\right)\right|-1,k\kappa \left(C_n\right)\right)$ $=\min \left(n-1,2k\right)=2k$ ，由引理2.6，$\kappa \left(C_n^k\right)\ge \min \left(\left|V\left(C_n\right)\right|-1,k\kappa \left(C_n\right)\right)=2k$ 。因$C_n^k$ 为2k-正则图，又由引理2.4，知$\kappa \left(C_n^k\right)\le \delta \left(C_n^k\right)=2k$ 。因此，$\kappa \left(C_n^k\right)=2k$ 。□

引理3.2：当$1\le k<\lfloor \frac{n}{2}\rfloor$ 时，图$C_n^k$ 的边连通度等于2k，即$\lambda \left(C_n^k\right)=2k$ 。

证明：由定理2.3，知$C_n^k$ 是点可迁图。由引理2.5，知$\lambda \left(C_n^k\right)=2k$ 。□

综合上述结论，我们得到$C_n^k$ 的点连通度和边连通度有如下结果：

定理3.3：当$1\le k<\lfloor \frac{n}{2}\rfloor$ 时，$C_n^k$ 的点连通度和边连通度都等于$2k$ ，即$\kappa \left(C_n^k\right)=\lambda \left(C_n^k\right)=2k$ 。

下面我们讨论$C_n^k$ 的限制边连通度。

定理3.4：当$n\ge 4$ 时，图$C_n^k$ 的限制边连通度${\lambda }_{\text{2}}\left(C_n^k\right)=\text{2}\lambda \left(C_n^k\right)-2$ 。

证明：当$k\ge \lfloor \frac{n}{2}\rfloor$ 时，$C_n^k$ 为完全图，此时$\lambda \left(C_n^k\right)=n-1$ 。假设X是$V\left(C_n^k\right)$ 的子集，$Y=\overline{X}=V\left(C_n^k\right)\backslash X$ ，且$\left|X\right|\ge 2$ ，$\left|Y\right|\ge 2$ ，不妨假设$\left|X\right|\le \left|Y\right|$ ，则$\left|E\left[X,Y\right]\right|=\left|X\right|\left(n-\left|X\right|\right)$ ，易知，当$\left|X\right|=2$ 或$n-2$ 时，$\left|E\left[X,Y\right]\right|$ 最小，且此时$\left|E\left[X,Y\right]\right|=2\left(n-2\right)=2n-4=2\left(n-1\right)-2=2\lambda \left(C_n^k\right)-2$ 。

下面我们只需考虑$1\le k<\lfloor \frac{n}{2}\rfloor$ 的情形。$C_n^k$ 为2k-正则图，此时$\lambda \left(C_n^k\right)=2k$ 。则对任意的边$v_i{v}_j\in E\left(C_n^k\right)$ ，有边度：$d\left(v_i\right)+d\left(v_j\right)-2=2k+2k-2=4k-2$ ，因此$C_n^k$ 的平凡限制边割为${\xi }_2\left(C_n^k\right)=\min \left\{d\left(v_i\right)+d\left(v_j\right)-2\right\}$ $=4k-2$ 。因此${\lambda }_2\left(C_n^k\right)\le {\xi }_2\left(C_n^k\right)=4k-2$ 。

下面我们证明${\lambda }_2\left(C_n^k\right)\ge 4k-2$ 。我们只需考虑$\left|X\right|,\left|Y\right|\ge 3$ 的情形，假设$\left|X\right|\le \left|Y\right|$ ，$\left|X\right|=p\ge 3$ 。

特别地，若$\left|X\right|=p=3$ ，则当$k=1$ 时，有$C_n^1=C_n$ ，$\partial \left(X\right)\ge d\left(v_i\right)+d\left(v_j\right)+d\left(v_s\right)-2\times 2=6k-4=\text{2}$ $={\xi }_2\left(C_n^1\right)=4k-2$ ，满足了$\partial \left(X\right)\ge 4k-2$ 。当$k\ge 2$ 时，$\partial \left(X\right)\ge d\left(v_i\right)+d\left(v_j\right)+d\left(v_s\right)-\text{3}\times 2=6k-\text{6}\ge 4k-2$ ，即$\partial \left(X\right)\ge 4k-2$ 。

现在我们假设$\left|X\right|=p$ ，且$p\ge \text{4}$ 。

情形1：$p\le k+1$

当$p\le k+1$ 时，每个点在X内部的度最多为$p-1$ ，p个点内部的边数最多为$\frac{p\left(p-1\right)}{2}$ 。此时$\partial \left(X\right)\ge p\cdot 2k-\frac{p\left(p-1\right)}{2}\times 2=p\left(2k-p+1\right)$ 。由于$p\le k+1$ ，$p\left(2k-p+1\right)\ge p\cdot k\ge 4k\ge 4k-2$ ，因此有$\partial \left(X\right)\ge 4k-2$ 。

情形2：$p>k+1$

在图$C_n^k$ 中总能找到两对在$C_n$ 中相邻的顶点$v_i,v_{i+1}$ 与$v_j,v_{j+1}$ ，其中一个点属于X，一个点属于Y，且有$v_i\in X,v_{i+1}\in Y,v_j\in Y,v_{j+1}\in X$ ，其中四个点各不相同。对于$v_i$ 与$v_{i+1}$ ，在$\mathrm{mod}n$ 情况下，含有它们的左边$k+1$ 阶极大完全子图记为$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ ，含有它们的右边$k+1$ 阶极大完全子图记为$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 。由于$\left|X\right|=p>k+1$ ，$\left|X\right|\le \left|Y\right|$ ，所以$n\ge 2k+4$ 。下面我们根据$v_j$ 和$v_{j+1}$ 与两个极大完全子图$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 与$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 的关系进行分类讨论，如“图3”所示情况。

情形2.1：$v_j$ 和$v_{j+1}$ 都不属于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 与$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 。

对于$v_i$ 与$v_{i+1}$ ，取$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ ($\mathrm{mod}n$ 情况下)，此时点$v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_{i-1}$ 要么属于X，要么属于Y，则这$k-1$ 个点向$v_i$ 和$v_{i+1}$ 所连的边有一条属于$E\left[X,Y\right]$ ，即在$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 中至少有$k-1$ 条边属于$E\left[X,Y\right]$ 。由于$n\ge 2k+4$ ，所以对于$v_i$ 与$v_{i+1}$ ，$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 中的点与$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 中的点除$v_i$ 与$v_{i+1}$ 外无重复($\mathrm{mod}n$ 情况下)。同理，$v_{i+2},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}$ 这$k-1$ 个点向$v_i$ 和$v_{i+1}$ 所连的边有一条属于$E\left[X,Y\right]$ ，即在$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 中至少有$k-1$ 条边属于$E\left[X,Y\right]$ 。这$2k-2$ 条边必以$v_i$ 或$v_{i+1}$ 作为某一端的端点。对于$v_j$ 与$v_{j+\text{1}}$ ，同理有$G[v_{j-k},v_{j-k+1},\cdot \cdot \cdot ,v_j,v_{j+1}]$ 与$G[v_j,v_{j+1},\cdot \cdot \cdot ,v_{j+k},v_{j+k+1}]$ ($\mathrm{mod}n$ 情况下)各有至少$k-1$ 条边属于$E\left[X,Y\right]$ 。这$2k-2$ 条边必以$v_j$ 或$v_{j+\text{1}}$ 作为某一端的端点。因为$v_j$ 和$v_{j+\text{1}}$ 都不属于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 与$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ ，所以在这$\text{4}k-\text{4}$ 条边中以$v_i$ 或$v_{i+1}$ 为端点则必不以$v_j$ 或$v_{j+\text{1}}$ 为端点，因此这$\text{4}k-\text{4}$ 条边中无重复边。且有边$v_i{v}_{i+1}\in E\left[X,Y\right]$ ，边$v_j{v}_{j+1}\in E\left[X,Y\right]$ ，此时$E\left[X,Y\right]$ 至少有$\left(k-1\right)\times 4+2=4k-2$ 条边，即$\partial \left(X\right)=E\left[X,Y\right]\ge 4k-2$ 。

Figure 3. The three situations of $p>k+1$

图3. $p>k+1$ 的3种情形

情形2.2：$v_j$ 或$v_{j+\text{1}}$ 中恰有一个点属于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 或$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 。

此时要么$v_j=v_{i-k-1},v_{j+1}=v_{i-k}$ ，要么$v_j=v_{i+k+1},v_{j+1}=v_{i+k+2}$ ，不失一般性，设$v_j=v_{i-k-1},v_{j+1}=v_{i-k}$ $\left(\mathrm{mod}n\right)$ 。对于$v_i$ 与$v_{i+1}$ ，同理$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 与$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 各有至少$k-1$ 条边属于$E\left[X,Y\right]$ ，这$2k-2$ 条边必以$v_i$ 或$v_{i+1}$ 作为某一端的端点，且除了边$v_{i+1}{v}_{j+1}$ 外所有边均不以$v_j$ 或$v_{j+\text{1}}$ 作为端点。对于$v_j$ 与$v_{j+\text{1}}$ ，同理有$G\left[v_{j-k},v_{j-k+1},\cdot \cdot \cdot ,v_j,v_{j+1}\right]$ 与$G\left[v_j,v_{j+1},\cdot \cdot \cdot ,v_{j+k},v_{j+k+1}\right]$ 各有至少$k-1$ 条边属于$E\left[X,Y\right]$ ，这$2k-2$ 条边必以$v_j$ 或$v_{j+\text{1}}$ 作为某一端的端点，且除了边$v_j{v}_i$ 外所有边均不以$v_i$ 或$v_{i+1}$ 作为端点。因此这$4k-4$ 条边中无重复边。且有边$v_i{v}_{i+1}\in E\left[X,Y\right]$ ，边$v_j{v}_{j+1}\in E\left[X,Y\right]$ ，此时$E\left[X,Y\right]$ 至少有$\left(k-1\right)\times 4+2=4k-2$ 条边，即$\partial \left(X\right)=E\left[X,Y\right]\ge 4k-2$ 。

情形2.3：$v_j$ 和$v_{j+\text{1}}$ 都属于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 或$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 。

不失一般性，设$v_j$ 和$v_{j+\text{1}}$ 都属于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ $\left(\mathrm{mod}n\right)$ 。对于$v_i$ 与$v_{i+1}$ ，同理有$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 与$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 各有至少$k-1$ 条边属于$E\left[X,Y\right]$ ，这$2k-2$ 条边必以$v_i$ 或$v_{i+1}$ 作为某一端的端点，且除了边$v_i{v}_j,v_{i+1}{v}_{j+1}$ 这两条边外所有边均不以$v_j$ 或$v_{j+\text{1}}$ 作为端点。对于$v_j$ 与$v_{j+\text{1}}$ ，同理有$G\left[v_{j-k},v_{j-k+1},\cdot \cdot \cdot ,v_j,v_{j+1}\right]$ 与$G\left[v_j,v_{j+1},\cdot \cdot \cdot ,v_{j+k},v_{j+k+1}\right]$ 各有至少$k-1$ 条边属于$E\left[X,Y\right]$ ，这$2k-2$ 条边必以$v_j$ 或$v_{j+\text{1}}$ 作为某一端的端点，且除了边$v_i{v}_j,v_{i+1}{v}_{j+1}$ 这两条边外所有边均不以$v_i$ 或$v_{i+1}$ 作为端点。即在$4k-4$ 条边中只有$v_i{v}_j$ 与$v_{i+1}{v}_{j+1}$ 这两条边重复出现，其他边均无重复。此时还有$v_i{v}_{i+1}$ 与$v_j{v}_{j+1}$ 两条边属于$E\left[X,Y\right]$ ,$E\left[X,Y\right]\ge \left(k-1\right)\times 4-2+2=4k-4$ 。

由于$n\ge 2k+4$ ，所以在$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 与$G\left[v_i,v_{i+1},\cdot \cdot \cdot ,v_{i+k},v_{i+k+1}\right]$ 外至少有4个顶点。因为$v_j$ 和$v_{j+\text{1}}$ 都属于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ $\left(\mathrm{mod}n\right)$ ，因此除点$v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}$ 外的点要么全是属于X的顶点，要么全是属于Y的顶点，要么能找到一对相邻顶点，其中一个点属于X，一个点属于Y。

当其他点全是属于X的顶点时，由于$p\ge 4$ ，则Y中除$v_{i+1}$ 与$v_j$ 外的其他点(至少两个)一定位于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 中，此时点$v_{i+2}$ 与点$v_{i-k-1}$ 对Y中除$v_{i+1}$ 与$v_j$ 外的点的连边至少有两条。

当其他点全是属于Y的顶点时，由于$p\ge 4$ ，则X中除$v_{j+\text{1}}$ 与$v_i$ 外的其他点(至少两个)一定位于$G\left[v_{i-k},v_{i-k+1},\cdot \cdot \cdot ,v_i,v_{i+1}\right]$ 中，此时点$v_{i+2}$ 与点$v_{i-k-1}$ 对X中除$v_{j+\text{1}}$ 与$v_i$ 外的点的连边至少有两条。

在这两种情况下，$E\left[X,Y\right]$ 至少有$\left(4k-4\right)+2=4k-2$ 条边，即$\partial \left(X\right)\ge 4k-2$ 。

当在这些点外找到一对相邻顶点$v_s,v_{s+1}$ ，其中一个点属于X，一个点属于Y时，总能找到一个不含$v_i,v_{i+1},v_j,v_{j+1}$ 的$k+1$ 阶极大完全子图包含了$v_s$ 与$v_{s+1}$ ，同理在此子图中，对于$v_s$ 与$v_{s+1}$ 至少有$k-1$ 条边属于$E\left[X,Y\right]$ ，且边$v_s{v}_{s+1}\in E\left[X,Y\right]$ 。此时$E\left[X,Y\right]$ 至少有$\left(4k-4\right)+\left(k-1\right)+1=5k-4\ge 4k-2$ 条边，即$\partial \left(X\right)\ge 4k-2$ 。

综上，$E\left[X,Y\right]=\partial \left(X\right)\ge 4k-2={\xi }_2\left(C_n^k\right)$ ，所以${\lambda }_2\left(C_n^k\right)\ge 4k-2$ 。

所以有${\lambda }_2\left(C_n^k\right)=4k-2=2\lambda \left(C_n^k\right)-2$ 。□

Example.$C_{10}^4$ 的连通性：

由定理3.3和定理3.4可知，点连通度$\kappa \left(C_{10}^4\right)=8$ ，边连通度$\lambda \left(C_{10}^4\right)=8$ ，限制边连通度${\lambda }_2\left(C_{10}^4\right)=4\times 4-2=14$ 。由“图2”可知，$C_{10}^4$ 中$\left\{v_{2,}{v}_3,v_4,v_5,v_7,v_8,v_9,v_{10}\right\}$ 构成了它的一个最小点割集，即$\kappa \left(C_{10}^4\right)=8$ ；与点$v_1$ 所关联的所有边构成了它的一个最小边割集，即$\lambda \left(C_{10}^4\right)=8$ ；除去边$v_1{v}_2$ 外与点$v_1,v_2$ 所关联的所有边构成了它的一个最小限制边割集，即${\lambda }_2\left(C_{10}^4\right)=14$ 。

推论3.5：$C_n^k$ 是极大限制边连通的，${\lambda }_2$ -最优的。□

4. 总结

本文给出了圈的k阶幂图的点连通度、边连通度、限制边连通度的结果，而圈本身也是一个特殊的结构，它既是点可迁图，也是极大点(边)连通的，圈的幂图$C_n^k$ 也继承了其部分性质，是点可迁图同时也是极大限制边连通的，因此圈的幂图的连通性的研究方法可能会给研究点可迁图等一些图类提供一点思路。幂图的连通性研究在理论和应用方面都具有重要意义，虽然目前已经取得了一定成果，但仍存在许多挑战和未解决问题，未来的研究对高次幂图和拥有复杂结构的幂图的连通性仍需进一步深入探讨，以推动幂图理论的发展和应用。

致 谢

在本文的撰写过程中，我衷心感谢所有给予我支持与帮助的人，也将感谢本文的审稿人提出的宝贵意见。

基金项目

国家自然科学基金青年项目(No.12201471)。

NOTES

^*通讯作者。