Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults |
| |
Authors: | Sun-Yuan Hsieh Yu-Fen Weng |
| |
Affiliation: | (1) Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan, 701, Taiwan |
| |
Abstract: | A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P
1=〈u
1,u
2,…,u
n
〉 and P
2=〈v
1,v
2,…,v
n
〉 of G are said to be independent if u
1=v
1, u
n
=v
n
, and u
i
≠v
i
for all 1<i<n; and both are full-independent if u
i
≠v
i
for all 1≤i≤n. Moreover, P
1 and P
2 are independent starting at
u
1, if u
1=v
1 and u
i
≠v
i
for all 1<i≤n. A set of Hamiltonian paths {P
1,P
2,…,P
k
} of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at
u
1) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting
at u
1). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q
n
is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q
n
. In this paper, we show the following results:
1. |
When |F|≤n−4, Q
n
−F−{x,y} remains Hamiltonian-laceable, where x and y are any two vertices from different partite sets and n≥4.
|
2. |
When |F|≤n−2, Q
n
−F contains (n−|F|−1)-pairwise full-independent Hamiltonian paths between n−|F|−1 pairs of adjacent vertices, where n≥2.
|
3. |
When |F|≤n−2, Q
n
−F contains (n−|F|−1)-pairwise independent Hamiltonian paths starting at any vertex v in a partite set to n−|F|−1 distinct vertices in the other partite set, where n≥2.
|
4. |
When 1≤|F|≤n−2, Q
n
−F contains (n−|F|−1)-pairwise independent Hamiltonian paths between any two vertices from different partite sets, where n≥3.
|
|
| |
Keywords: | Graph-theoretic interconnection networks Hypercubes Hamiltonian Pairwise independent Hamiltonian paths Fault-tolerant embedding |
本文献已被 SpringerLink 等数据库收录! |
|