The spanning connectivity of the arrangement graphs

• We review some properties of the arrangement graph.
• We prove that there exists a set of disjoint paths in an incomplete arrangement graph.
• We prove that the arrangement graph An,kAn,k is k(n−k)∗k(n−k)∗-connected for n−k≥2n−k≥2.

A ww-container Cw(u,v)Cw(u,v) of a graph GG between two distinct vertices uu and vv is a set of ww disjoint paths between uu and vv. A ww-container Cw(u,v)Cw(u,v) is a w∗w∗-container if every vertex of GG is on some path in Cw(u,v)Cw(u,v). A graph GG is said to be w∗w∗-connected if there exists a w∗w∗-container between any two distinct vertices uu and vv. The connectivity of the arrangement graph An,kAn,k is k(n−k)k(n−k). In this paper, we prove that An,kAn,k is k(n−k)∗k(n−k)∗-connected for n−k≥2n−k≥2.