Panconnectivity, fault‐tolerant hamiltonicity and hamiltonian‐connectivity in alternating group graphs

Jwo et al. [Networks 23 (1993) 315–326] introduced the alternating group graph as an interconnection network topology for computing systems. They showed that the proposed structure has many advantages over n ‐cubes and star graphs. For example, all alternating group graphs are hamiltonian‐connected (i.e., every pair of vertices in the graph are connected by a hamiltonian path) and pancyclic (i.e., the graph can embed cycles with arbitrary length with dilation 1). In this article, we give a stronger result: all alternating group graphs are panconnected, that is, every two vertices x and y in the graph are connected by a path of length k for each k satisfying d ( x , y ) ≤ k ≤ | V | − 1, where d ( x , y ) denotes the distance between x and y , and | V | is the number of vertices in the graph. Moreover, we show that the r ‐dimensional alternating group graph AG r , r ≥ 4, is ( r − 3)‐vertex fault‐tolerant Hamiltonian‐connected and ( r − 2)‐vertex fault‐tolerant hamiltonian. The latter result can be viewed as complementary to the recent work of Lo and Chen [IEEE Trans. Parallel and Distributed Systems 12 (2001) 209–222], which studies the fault‐tolerant hamiltonicity in faulty arrangement graphs. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 302–310 2004