Hamiltonian connectivity of the WK-recursive network with faulty nodes
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| | F | -node Hamiltonian-connected if G-F G - F is Hamiltonian-connected. We use K(d,t) 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) K ( d , t ) is (d-4) ( d - 4 ) -node Hamiltonian-connected. Since the connectivity of K(d,t) K ( d , t ) is d-1 d - 1 , the result is optimal in the worst case.
wk-recursive hamiltonian-connected graph-theoretic interconnection network fault-tolerant embedding