Fault-tolerant cycle-embedding in alternating group graphs

摘要

Cycle-embedding is an important issue in evaluating the efficiency of interconnection networks and is also an extension of the theoretical research on Hamiltonicity. In this paper, we study the fault-tolerant Hamiltonicity of alternating group graphs which were recently proposed as interconnection topologies for parallel and distributed systems. A cycle of length ℓ is said to be an ℓ-cycle. Let F be a set of faulty vertices in an n-dimensional alternating group graph AGn and let m be the number of vertices in AGn − F. A previous result 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] showed that, for n ⩾ 4, AGn − F is Hamiltonian (i.e., AGn − F possesses a Hamiltonian cycle) if ∣F∣ ⩽ n − 2, and AGn − F is Hamiltonian-connected (i.e., every two vertices of AGn − F are connected by a Hamiltonian path) if ∣F∣ ⩽ n − 3. In this paper, we show the following results: (i) AGn − F is pancyclic (i.e., AGn − F contains an ℓ-cycle for each ℓ with 3 ⩽ ℓ ⩽ m) if ∣F∣ ⩽ n − 2; (ii) AGn − F is vertex-pancyclic (i.e., every vertex of AGn − F is contained in an ℓ-cycle for each ℓ with 3 ⩽ ℓ ⩽ m) if ∣F∣ ⩽ n − 3; and (iii) AGn − F is edge 4-pancyclic (i.e., every edge of AGn − F is contained in an ℓ-cycle for each ℓ with 4 ⩽ ℓ ⩽ m) if ∣F∣ ⩽ n − 4. The first result is an improvement over the previous one and the last two results are new characterization of fault-tolerant pancyclicity on AGn. All the results we achieved are the best possible in the sense that the number of faulty vertices cannot be increased.