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) less than or equal to k less than or equal to \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 greater than or equal to 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) 209222], which studies the fault-tolerant hamiltonicity in faulty arrangement graphs. (C) 2004 Wiley Periodicals, Inc.