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 条
  • [1] Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs
    Kikuchi, Yosuke
    Araki, Toru
    INFORMATION PROCESSING LETTERS, 2006, 100 (02) : 52 - 59
  • [2] Edge-fault-tolerant edge-bipancyclicity of bubble-sort graphs
    Xu, Xin Ping
    Xu, Min
    Jing, Jin
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2012, 28 (04) : 675 - 686
  • [3] Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees
    Li, Hengzhe
    Yang, Weihua
    Meng, Jixiang
    DISCRETE MATHEMATICS, 2012, 312 (21) : 3087 - 3095
  • [4] Edge-Fault-Tolerant Edge-Bipancyclicity of Bubble-Sort Graphs
    Xin Ping XU
    Min XU
    Jin JING
    Acta Mathematica Sinica,English Series, 2012, (04) : 675 - 686
  • [5] Edge-fault-tolerant edge-bipancyclicity of bubble-sort graphs
    Xin Ping Xu
    Min Xu
    Jin Jing
    Acta Mathematica Sinica, English Series, 2012, 28 : 675 - 686
  • [6] Edge-fault-tolerant edge-bipancyclicity of hypercubes
    Xu, JM
    Du, ZZ
    Xu, M
    INFORMATION PROCESSING LETTERS, 2005, 96 (04) : 146 - 150
  • [7] Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes
    Li, TK
    Tsai, CH
    Tan, JJM
    Hsu, LH
    INFORMATION PROCESSING LETTERS, 2003, 87 (02) : 107 - 110
  • [8] Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges
    Cheng, Chia-Wen
    Hsieh, Sun-Yuan
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2016, 82 (05) : 767 - 781
  • [9] FAULT-TOLERANT MAXIMAL LOCAL-CONNECTIVITY ON CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES
    Shih, Lun-Min
    Chiang, Chieh-Feng
    Hsu, Lih-Hsing
    Tan, Jimmy J. M.
    JOURNAL OF INTERCONNECTION NETWORKS, 2009, 10 (03) : 253 - 260
  • [10] Edge-fault-tolerant pancyclicity of arrangement graphs
    Sun, Sainan
    Xu, Min
    Wang, Kaishun
    INFORMATION SCIENCES, 2014, 285 : 50 - 62
12345