Hamiltonian laceability of bubble-sort graphs with edge faults

被引：52
作者：
Araki, Toru
Kikuchi, Yosuke
机构：
[1] Iwate Univ, Dept Comp & Informat Sci, Morioka, Iwate 0208551, Japan
[2] Tsuyama Natl Coll Technol, Dept Elect & Comp Engn, Tsuyama, Okayama 7088509, Japan
来源：
INFORMATION SCIENCES | 2007年 / 177卷 / 13期
关键词：
bubble-sort graph; Hamiltonian laceability; strongly hamiltonian laceability; hyper-hamiltonian laceability; Hamiltonian cycle; fault-tolerance;
D O I：
10.1016/j.ins.2007.01.017
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
It is known that the n-dimensional bubble-sort graph B-n is bipartite, (n - 1)-regular, and has n! vertices. We first show that, for any vertex v, B-n - v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of B-n. We next show that B-n - F has a hamiltonian path between any two vertices of different partite sets if vertical bar F vertical bar is at most n - 3. Then we also prove that B-n - F has a path of length n! - 2 between any pair of vertices in the same partite set. (C) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码：2679 / 2691
页数：13
相关论文
共 50 条
  • [41] Conditional Connectivity of Bubble Sort Graphs
    Ling-sheng SHI
    Peng WU
    [J]. ActaMathematicaeApplicataeSinica, 2017, 33 (04) : 933 - 944
  • [42] Diagnosability of bubble-sort graph networks under the comparison diagnosis model
    Ren, Yunxia
    Wang, Shiying
    [J]. 2015 INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND COMMUNICATION NETWORKS (CICN), 2015, : 823 - 826
  • [43] Conditional connectivity of bubble sort graphs
    Ling-sheng Shi
    Peng Wu
    [J]. Acta Mathematicae Applicatae Sinica, English Series, 2017, 33 : 933 - 944
  • [44] Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks
    Kao, Shih-Shun
    Pai, Kung-Jui
    Hsieh, Sun-Yuan
    Wu, Ro-Yu
    Chang, Jou-Ming
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) : 972 - 986
  • [45] The (strong) structure connectivity and (strong) substructure connectivity of the (n, k)-bubble-sort network
    Guo, Jia
    Lu, Mei
    Wang, Xin
    [J]. APPLIED MATHEMATICS AND COMPUTATION, 2022, 425
  • [46] Fault tolerance of hypercube like networks: Spanning laceability under edge faults
    Xu, Min
    Naik, Kshirasagar
    Thulasiraman, Krishnaiyan
    [J]. THEORETICAL COMPUTER SCIENCE, 2020, 835 (835) : 44 - 57
  • [47] Reliability evaluation of Modified bubble-sort graph networks based on structure fault pattern
    Wang, Na
    Meng, Jixiang
    Tian, Yingzhi
    [J]. APPLIED MATHEMATICS AND COMPUTATION, 2022, 430
  • [48] Double declined subnetwork reliability analysis in bubble-sort networks under node fault model
    Meng, Kaiyue
    Yang, Yuxing
    [J]. THEORETICAL COMPUTER SCIENCE, 2025, 1023
  • [49] The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks
    Wang, Shiying
    Wang, Zhenhua
    Wang, Mujiangshan
    [J]. COMPUTER JOURNAL, 2016, 59 (12) : 1839 - 1856
  • [50] The g-Good-Neighbor Diagnosability of Bubble-Sort Graphs under Preparata, Metze, and Chien's (PMC) Model and Maeng and Malek's (MM)* Model
    Wang, Shiying
    Wang, Zhenhua
    [J]. INFORMATION, 2019, 10 (01)
12345