Edge-Fault-Tolerant Pancyclicity of Alternating Group Graphs

被引：6
|
作者：
Tsai, Ping-Ying [1 ]
Chen, Gen-Huey [1 ]
Fu, Jung-Sheng [2 ]
机构：
[1] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei 10764, Taiwan
[2] Natl United Univ, Dept Elect Engn, Miaoli, Taiwan
来源：
NETWORKS | 2009年 / 53卷 / 03期
关键词：
alternating group graph; Cayley graph; cycle embedding; fault tolerance; pancycle; INTERCONNECTION NETWORKS; HAMILTONIAN-CONNECTIVITY; AUGMENTED CUBES; STAR GRAPHS; N-CUBES; PANCONNECTIVITY; CYCLES;
D O I：
10.1002/net.20291
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The alternating group graph, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. Previously, the alternating group graph was shown to be pancyclic, i.e., containing cycles of all possible lengths. In this article, we further show that the alternating group graph remains pancyclic, even if there are up to 2n - 6 edge faults, where n >= 3 is the dimension of the alternating group graph. The result is optimal with respect to the number of edge faults tolerated. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 53(3), 307-313 2009
引用
收藏
页码：307 / 313
页数：7
相关论文
共 50 条
  • [41] Fault-tolerant pancyclicity of the Mobius cubes
    Yang, MC
    Li, TK
    Tan, JJM
    Hsu, LH
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2005, E88A (01) : 346 - 352
  • [42] Conditional edge-fault pancyclicity of augmented cubes
    Cheng, Dongqin
    Hao, Rong-Xia
    Feng, Yan-Quan
    THEORETICAL COMPUTER SCIENCE, 2013, 510 : 94 - 101
  • [43] (n-2)-Fault-Tolerant Edge-Pancyclicity of Crossed Cubes CQn
    Xu, Xirong
    Zhang, Huifeng
    Wang, Ziming
    Zhang, Qiang
    Zhang, Peng
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2021, 32 (03) : 289 - 304
  • [44] Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults
    Hsieh, Sun-Yuan
    Wu, Chang-De
    JOURNAL OF SUPERCOMPUTING, 2009, 49 (03): : 354 - 372
  • [45] Edge-bipancyclicity of star graphs under edge-fault tolerant
    Xu, Min
    Hu, Xiao-Dong
    Zhu, Qiang
    APPLIED MATHEMATICS AND COMPUTATION, 2006, 183 (02) : 972 - 979
  • [46] Structure and substructure connectivity of alternating group graphs
    Li, Xiaowang
    Zhou, Shuming
    Ren, Xiangyu
    Guo, Xia
    APPLIED MATHEMATICS AND COMPUTATION, 2021, 391
  • [47] The edge fault-tolerant two-disjoint path covers of Cayley graphs generated by a transposition tree
    Qiao, Hongwei
    Meng, Jixiang
    Sabir, Eminjan
    DISCRETE APPLIED MATHEMATICS, 2024, 356 : 174 - 181
  • [48] Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees
    Li, Hengzhe
    Yang, Weihua
    Meng, Jixiang
    DISCRETE MATHEMATICS, 2012, 312 (21) : 3087 - 3095
  • [49] Minimum Neighborhood of Alternating Group Graphs
    Huang, Yanze
    Lin, Limei
    Wang, Dajin
    Xu, Li
    IEEE ACCESS, 2019, 7 : 17299 - 17311
  • [50] Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults
    Sun-Yuan Hsieh
    Chang-De Wu
    The Journal of Supercomputing, 2009, 49 : 354 - 372
12345