Panpositionable hamiltonicity of the alternating group graphs

Abstract

The alternating group graph AG(n) is an interconnection network topology based on the Cayley graph of the alternating group. There are some interesting results concerning the hamiltonicity and the fault tolerant hamiltonicity of the alternating group graphs. In this article, we propose a new concept called panpositionable harniltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer I satisfying d(x, y) <= I <= vertical bar V(G)vertical bar - d(x, y), there exists a hamiltonian cycle C of G such that the relative distance between x, y on C is I. We show that AG(n) is panpositionable hamiltonian if n >= 3. (C) 2007 Wiley Periodicals, Inc.