Hamiltonian laceability of bubble-sort graphs with edge faults

被引：51
作者：
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 条
  • [21] The container problem in bubble-sort graph
    Suzuki, Yasuto
    Kaneko, Keiichi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2008, E91D (04): : 1003 - 1009
  • [22] Fault-tolerant Maximal Local-Connectivity on the Bubble-sort Graphs
    Shih, Lun-Min
    Tan, Jimmy J. M.
    PROCEEDINGS OF THE 2009 SIXTH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY: NEW GENERATIONS, VOLS 1-3, 2009, : 564 - 569
  • [23] Subnetwork preclusion for bubble-sort networks
    Yang, Yuxing
    Wang, Shiying
    Li, Jing
    INFORMATION PROCESSING LETTERS, 2015, 115 (11) : 817 - 821
  • [24] Hamiltonian-laceability of star graphs
    Hsieh, SY
    Chen, GH
    Ho, CW
    NETWORKS, 2000, 36 (04) : 225 - 232
  • [25] Subnetwork reliability analysis of bubble-sort graph networks
    Feng, Kai
    Ma, Xinyu
    Wei, Wei
    THEORETICAL COMPUTER SCIENCE, 2021, 896 : 98 - 110
  • [26] Embedding Algorithms for Star, Bubble-Sort, Rotator-Faber-Moore, and Pancake Graphs
    Kim, Mihye
    Kim, Dongwan
    Lee, Hyeongok
    ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, PT 2, PROCEEDINGS, 2010, 6082 : 348 - +
  • [27] Reliability assessment for modified bubble-sort networks
    Chen, Ling
    Li, Xiang-Jun
    Ma, Meijie
    DISCRETE APPLIED MATHEMATICS, 2022, 307 : 88 - 94
  • [28] Fault Tolerance of Bubble-sort Networks on Components
    Guo, Litao
    JOURNAL OF INTERNET TECHNOLOGY, 2021, 22 (03): : 637 - 643
  • [29] Path and cycle fault tolerance of bubble-sort graph networks
    Zhang, Guozhen
    Lin, Shangwei
    THEORETICAL COMPUTER SCIENCE, 2019, 779 : 8 - 16
  • [30] 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
12345