圈的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$ .