Hamiltonian laceability of bubble-sort graphs with edge faults |
| |
| Authors: | Toru Araki Yosuke Kikuchi |
| |
| Affiliation: | a Department of Computer and Information Sciences, Iwate University, 4-3-5 Ueda, Morioka, Iwate 020-8551, Japan
b Department of Electronics and Computer Engineering, Tsuyama National College of Technology, Tsuyama, Okayama 708-8509, Japan |
| |
| Abstract: | It is known that the n-dimensional bubble-sort graph Bn is bipartite, (n − 1)-regular, and has n! vertices. We first show that, for any vertex v, Bn − v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of Bn. We next show that Bn − F has a hamiltonian path between any two vertices of different partite sets if ∣F∣ is at most n − 3. Then we also prove that Bn − F has a path of length n! − 2 between any pair of vertices in the same partite set. |
| |
| Keywords: | Bubble-sort graph Hamiltonian laceability Strongly hamiltonian laceability Hyper-hamiltonian laceability Hamiltonian cycle Fault-tolerance |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
