Fault-tolerant Hamiltonicity in a class of faulty meshes

摘要

This paper addresses the Hamiltonian properties of rectangular meshes with faulty nodes. We present a necessary and sufficient condition for an m × n mesh (m ⩾ 4 and n ⩾ 4 are even) with two faulty nodes to have a fault-free Hamiltonian cycle, which generalizes a result owing to Kim and Yoon [J.S. Kim, S.H. Yoon, Embedding of rings in 2-D meshes and tori with faulty nodes, Journal of Systems Architecture 43 (9) (1997) 643–654]. We also describe an efficient scheme for constructing such a fault-free Hamiltonian cycle, if there is.