Embedding Hamiltonian paths and Hamiltonian cycles in faulty pancake graphs
Chun‐Nan Hung, Kao-Yung Liang, Lih-Hsing Hsu · 2003
The use of pancake and star networks as an interconnection network has been studied by many researchers. The fault tolerance for Hamiltonian networks is also an important issue. In this paper, we prove that an n-dimensional faulty pancake graph contains a Hamiltonian cycle with |F| /spl les/ n - 3 faults. Furthermore, there exist Hamiltonian paths between two arbitrary but distinct nodes in a faulty pancake graph with |F| /spl les/ n - 4 faults.