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-FG-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-1d-1, the result is optimal in the worst case.