The Connectivity Of Arrangement Graphs

It is well-known that a topological structure for an interconnection network can be modeled by a connected graph G=(V, E), where V is the set of processors and E is the set of communication links in the network. The interconnection network has been an important research area for parallel and distributed computer systems.This paper mainly investigate the spanning connectivity of arrangement graphs. The arrangement graph was proposed by Day and Tripathi as a generalization of the star graph. It has many good properties such as:hierarchical structure, vertex and edge symmetry. Arrangement graphs is isomorphic to complete graph when n≥2, k=1. When n≥3, k≠n-1, it is not bipartite graph.In the first chapter, some definitions are given. In the following three chapters, we investigate the spanning connectivity of An,k according to different conditions. The main results of this paper are as follows:Conclusion (1) The arrangement graph An,2is super spanning connected, when n≥5.Conclusion (2) The arrangement graph An,k is3*-connected and4*-connected, when n≥6, n-k≥3.Conclusion (3) The arrangement graph An,k is [k(n-k)]*-connected, when k≥3,n-k≥4.Conclusion (4) The arrangement graph An,k is s*-connected, for any s,(k-1)(n-k)<s<k(n-k),k≥3,n-k≥4.