首页 | 本学科首页   官方微博 | 高级检索  
     


Embedding Hamiltonian cycles in alternating group graphs under conditional fault model
Authors:Ping-Ying Tsai  Jung-Sheng Fu
Affiliation:a Department of Computer Science and Information Engineering, Hwa Hsia Institute of Technology, Taipei 23568, Taiwan, ROC
b Department of Electronics Engineering, National United University, Miaoli, Taiwan, ROC
c Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC
Abstract:In this paper, assuming that each node is incident with two or more fault-free links, we show that an n-dimensional alternating group graph can tolerate up to 4n − 13 link faults, where n ? 4, while retaining a fault-free Hamiltonian cycle. The proof is computer-assisted. The result is optimal with respect to the number of link faults tolerated. Previously, without the assumption, at most 2n − 6 link faults can be tolerated for the same problem and the same graph.
Keywords:Alternating group graph   Cayley graph   Conditional fault   Fault tolerance   Hamiltonian cycle
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号