Fault-tolerant cycle-embedding in alternating group graphs

作者：Chang Jou Ming^*; Yang Jinn Shyong

来源：Applied Mathematics and Computation, 2008, 197(2): 760-767.

DOI：10.1016/j.amc.2007.08.010

• hamiltonicity
• pancyclicity
• panconnectivity
• graph embedding
• fault tolerance
• interconnection networks
• 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 l is said to be an l-cycle. Let F be a set of faulty vertices in an n-dimensional alternating group graph AG(n) and let m be the number of vertices in AG(n)-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, AG(n) - F is Hamiltonian (i.e., AG(n) - F possesses a Hamiltonian cycle) if |F| <= n - 2, and AG(n) - F is Hamiltonian-connected (i.e., every two vertices of AG(n) - F are connected by a Hamiltonian path) if |F| <= n - 3. In this paper, we show the following results: (i) AG(n) - F is pancyclic (i.e., AG(n) - F contains an l-cycle for each l with 3 <= l <= m) if |F| <= n - 2; (ii) AG(n) - F is vertex-pancyclic (i.e., every vertex of AG(n) - F is contained in an l-cycle for each l with 3 <= l <= m) if |F| <= n - 3; and (iii) AG(n) - F is edge 4-pancyclic (i.e., every edge of AG(n) - F is contained in an l-cycle for each l with 4 <= l <= 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 AG(n). All the results we achieved are the best possible in the sense that the number of faulty vertices cannot be increased.

• 出版日期2008-4-1