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
相关论文
共 16 条
[1]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[2]   Complete path embeddings in crossed cubes [J].
Fan, Jianxi ;
Jia, Xiaohua ;
Lin, Xiaola .
INFORMATION SCIENCES, 2006, 176 (22) :3332-3346
[3]   Longest fault-free paths in hypercubes with vertex faults [J].
Fu, JS .
INFORMATION SCIENCES, 2006, 176 (07) :759-771
[4]  
Hsieh SY, 2000, NETWORKS, V36, P225, DOI 10.1002/1097-0037(200012)36:4<225::AID-NET3>3.0.CO
[5]  
2-G
[6]   Solving the path cover problem on circular-arc graphs by using an approximation algorithm [J].
Hung, RW ;
Chang, MS .
DISCRETE APPLIED MATHEMATICS, 2006, 154 (01) :76-105
[7]   On the k-path cover problem for cacti [J].
Jin, ZM ;
Li, XL .
THEORETICAL COMPUTER SCIENCE, 2006, 355 (03) :354-363
[8]   Node-to-node internally disjoint paths problem in bubble-sort graphs [J].
Kaneko, K ;
Suzuki, Y .
10TH IEEE PACIFIC RIM INTERNATIONAL SYMPOSIUM ON DEPENDABLE COMPUTING, PROCEEDINGS, 2004, :173-182
[9]   Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs [J].
Kikuchi, Yosuke ;
Araki, Toru .
INFORMATION PROCESSING LETTERS, 2006, 100 (02) :52-59
[10]   SYMMETRY IN INTERCONNECTION NETWORKS BASED ON CAYLEY-GRAPHS OF PERMUTATION-GROUPS - A SURVEY [J].
LAKSHMIVARAHAN, S ;
JWO, JS ;
DHALL, SK .
PARALLEL COMPUTING, 1993, 19 (04) :361-407
12