Hamiltonian connectivity of the WK-recursive network with faulty nodes |
| |
Authors: | Jung-Sheng Fu |
| |
Affiliation: | Department of Electronic Engineering, National United University, 1, Lien Da, Kung-Ching Li, Miaoli 36003, Taiwan |
| |
Abstract: | A graph G is said to be Hamiltonian-connected if there is a Hamiltonian path between every two distinct nodes of G. Let F denote the set of faulty nodes of G. Then, G is |F|-node Hamiltonian-connected if G-F is Hamiltonian-connected. We use K(d,t) to denote a WK-recursive network of level t, each of whose basic modules is a d-node complete graph. Compared with other networks, it is rather difficult to construct a Hamiltonian path between two arbitrary nodes in a faulty WK-recursive network. In this paper, we show that K(d,t) is (d-4)-node Hamiltonian-connected. Since the connectivity of K(d,t) is d-1, the result is optimal in the worst case. |
| |
Keywords: | Graph-theoretic interconnection network WK-recursive Fault-tolerant embedding Hamiltonian-connected |
本文献已被 ScienceDirect 等数据库收录! |
|