Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees

被引：4
|
作者：
Yang, Weihua [1 ]
Li, Hengzhe [2 ]
He, Wei-hua [3 ]
机构：
[1] Taiyuan Univ Technol, Dept Math, Taiyuan 030024, Shanxi, Peoples R China
[2] Henan Normal Univ, Coll Math & Informat Sci, Xinxiang 453007, Peoples R China
[3] Univ Paris 11, CNRS, UMR 8623, Lab Rech Informat, F-91405 Orsay, France
来源：
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 2015年 / 92卷 / 07期
关键词：
bipancyclicity; Cayley graphs; edge-fault-tolerant bipancyclicity; symmetric group; 05C12; 68M10; 05A10; HYPER HAMILTONIAN LACEABILITY; STAR GRAPHS; INTERCONNECTION NETWORKS; MOBIUS CUBES; PANCYCLICITY; LINK;
D O I：
10.1080/00207160.2014.953942
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The Cayley graphs on the symmetric group plays an important role in the study of Cayley graphs as interconnection networks. Let Cay(S-n, B) be the Cayley graphs generated by transposition-generating trees. It is known that for any F subset of E(Cay(S-n, B)), if |F|<= n-3 and n >= 4, then there exists a hamiltonian cycle in Cay(Sn, B)-F. In this paper, we show that Cay(S-n, B)-F is bipancyclic if Cay(S-n, B) is not a star graph, for n >= 4 and |F|<= n-3.
引用
收藏
页码：1345 / 1352
页数：8
相关论文
共 50 条
  • [21] Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model
    Chang, Naiwen
    Cheng, Eddie
    Hsieh, Sunyuan
    ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2015, 20 (02)
  • [22] Fault-Tolerant Strongly Hamiltonian Laceability and Hyper-Hamiltonian Laceability of Cayley Graphs Generated by Transposition Trees
    Xue, Shudan
    Deng, Qingying
    Li, Pingshan
    COMPUTER JOURNAL, 2023, 66 (02) : 384 - 398
  • [23] Diagnosability of Cayley graphs generated by transposition trees with missing edges
    Cheng, Eddie
    Liptak, Laszlo
    INFORMATION SCIENCES, 2013, 238 : 250 - 252
  • [24] Cyclic Vertex-Connectivity of Cayley Graphs Generated by Transposition Trees
    Cheng, Eddie
    Liptak, Laszlo
    Qiu, Ke
    Shen, Zhizhang
    GRAPHS AND COMBINATORICS, 2013, 29 (04) : 835 - 841
  • [25] Cyclic Vertex-Connectivity of Cayley Graphs Generated by Transposition Trees
    Eddie Cheng
    László Lipták
    Ke Qiu
    Zhizhang Shen
    Graphs and Combinatorics, 2013, 29 : 835 - 841
  • [26] 3-path-connectivity of Cayley graphs generated by transposition trees
    Jin, Qihui
    Li, Shasha
    Xie, Mengmeng
    DISCRETE APPLIED MATHEMATICS, 2023, 339 : 292 - 299
  • [27] Edge-fault-tolerant bipanconnectivity of hypercubes
    Wang, Hai-Liang
    Wang, Jian-Wei
    Xu, Jun-Ming
    INFORMATION SCIENCES, 2009, 179 (04) : 404 - 409
  • [28] Edge-fault-tolerant diameter and bipanconnectivity of hypercubes
    Chen, Xie-Bin
    INFORMATION PROCESSING LETTERS, 2010, 110 (24) : 1088 - 1092
  • [29] Edge-fault-tolerant node-pancyclicity of twisted cubes
    Yang, Ming-Chien
    INFORMATION PROCESSING LETTERS, 2009, 109 (21-22) : 1206 - 1210
  • [30] Fault resiliency of Cayley graphs generated by transpositions
    Cheng, Eddie
    Liptak, Laszlo
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2007, 18 (05) : 1005 - 1022
12345