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

On Connectivity of the kth Power of Paths

设G是连通图,G的k阶幂图G^(k)是一个与G具有相同顶点集的图,G^(k)中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图P_(n)^(k)的点连通度κ(P_(n)^(k))、边连通度λ(P_(n)^(k))和限制边连通度λ_(2)(P_(n)^(k)).得到:当n>k时,κ(P_(n)^(k))=λ(P_(n)^(k))=k;关于限制边连通度:当2≤n≤k+1时λ_(2)(P_(n)^(k))=2n-4,当n>k+1时,λ_(2)(P_(n)^(k))=2k-1.

Let G be a connected graph.The k th power G^(k)of G is a graph having the same vertex set of G such that the two vertexes 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 k(P_(n)^(k)),edge connectivityλ(P_(n)^(k))and restricted edge connectivityλ_(2)(P_(n)^(k))of P_(n)^(k)are studied.We obtain the following results:κ(P_(n)^(k))=λ(P_(n)^(k))=k when n>k;λ_(2)(P_(n)^(k))=2n-4 when 2≤n≤k+1 andλ_(2)(P_(n)^(k))=2k-1 when n>k+1。