排列图的若干k^＊-连通性

Some Properties of Arrangement Graphs A_(n,k)

排列图An,k是星图的推广,但它的阶却比星图有更好的灵活性.证明了:当n5,n-k3时,排列图An,k为3*-连通图;当n6,n-k3时,排列图An,k为4*-连通图.

The arrangement graphs An,k is a generalization of the star graphs, yet it is more flexible in its size than the Star Graphs. This paper proves that the arrangement graphs An,k is 3 ＊ - connected in the case of n≥5, n-k ≥3 and 4^＊- connected in the case of n≥ 6, n -k≥3.