Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs
Keiichi Kaneko · IEICE Transactions on Information and Systems · 2007
Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n-2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n - 3 or less.