An optimal result on fault-tolerant cycle-embedding in alternating group graphs

The alternating group graph was proposed as an interconnection network topology for computing systems. It has many advantages over n-cubes and star graphs. Let F be a set of faulty vertices in an n-dimensional alternating group graph AGn. A cycle of length ℓ is said to be an ℓ-cycle. A previous result in [J.-M. Chang, J.-S. Yang, Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760–767] showed that, for n⩾4, AGn−F is pancyclic (i.e., AGn−F contains an ℓ-cycle for each ℓ with 3⩽ℓ⩽|V(AGn−F)|) if |F|⩽n−2. Although the fault-tolerances of AG4 are tight, the results are not optimal for n⩾5. In this paper, for the same problem, we give an optimal result: for n⩾4, AGn−F is pancyclic if |F|⩽2n−6. Since a graph G is pancyclic, then clearly it is hamiltonian. Thus, for n⩾4, AGn−F is also hamiltonian if |F|⩽2n−6. This result is also an improvement over the previous ones given in [J.-M. Chang, J.-S. Yang, Y.-L. Wang, Y. Cheng, Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs, Networks 44 (2004) 302–310].