Mutually independent Hamiltonian cycles in alternating group graphs

The alternating group graph has been used as the underlying topology for many practical multicomputers, and has been extensively studied in the past. In this article, we will show that any alternating group graph AG _n , where n??3 is an integer, contains 2n?4 mutually independent Hamiltonian cycles. More specifically, let N=|V(AG _n )|, v _i ??V(AG _n ) for 1??i??N, and ??v ₁,v ₂,??,v _N ,v ₁?? be a Hamiltonian cycle of AG _n . We show that AG _n contains 2n?4 Hamiltonian cycles, denoted by $C_{l}=\langle v_{1},v_{2}^{l},\ldots,v_{N}^{l},v_{1}\rangle$ for 1??l??2n?4, such that $v_{i}^{l} \ne v_{i}^{l'}$ for all 2??i??N whenever l??l??. The result is optimal since each vertex of AG _n has exactly 2n?4 neighbors.