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 条

[31] (n-3)-edge-fault-tolerant weak-pancyclicity of (n, k)-star graphs
Duh, Dyi-Rong
Chen, Tzu-Lung
Wang, Yue-Li
THEORETICAL COMPUTER SCIENCE, 2014, 516 : 28 - 39
[32] Edge-fault-tolerant vertex-pancyclicity of augmented cubes
Fu, Jung-Sheng
INFORMATION PROCESSING LETTERS, 2010, 110 (11) : 439 - 443
[33] Bounds for neighbor connectivity of Cayley graphs generated by trees and unicyclic graphs
Abdallah, Mohamad
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2024, 12 (02) : 343 - 362
[34] Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults
Hsieh, Sun-Yuan
Wu, Chang-Yu
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 19 (01) : 16 - 30
[35] Edge-fault-tolerant panconnectivity and edge-pancyclicity of the complete graph
Chen, Xie-Bin
INFORMATION SCIENCES, 2013, 235 : 341 - 346
[36] Fault-Tolerant Cycle Embedding in Cartesian Product Graphs: Edge-Pancyclicity and Edge-Bipancyclicity with Faulty Edges
Cheng, Chia-Wen
Hsieh, Sun-Yuan
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (11) : 2997 - 3011
[37] Edge-fault-tolerant strong Menger edge connectivity on the class of hypercube-like networks
Li, Pingshan
Xu, Min
DISCRETE APPLIED MATHEMATICS, 2019, 259 : 145 - 152
[38] Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model
Yang, Da-Wei
Feng, Yan-Quan
Kwak, Jin Ho
Zhou, Jin-Xin
INFORMATION SCIENCES, 2016, 329 : 317 - 328
[39] Conditional edge-fault-tolerant Hamiltonicity of dual-cubes
Chen, Jheng-Cheng
Tsai, Chang-Hsiung
INFORMATION SCIENCES, 2011, 181 (03) : 620 - 627
[40] Automorphism groups of Cayley graphs generated by connected transposition sets
Ganesan, Ashwin
DISCRETE MATHEMATICS, 2013, 313 (21) : 2482 - 2485

← 1 2 3 4 5 →