Fault-Hamiltonicity of Cartesian products of directed cycles

  • Chun-Nan Hung
  • Tao-Ming Wang
  • Lih-Hsing Hsu
  • Eddie Cheng


Although the Cartesian product of two Hamiltonian graphs is Hamiltonian, the corresponding statement for directed graphs is not true. Indeed, it is known that it does not always hold even for the Cartesian products of two directed cycles. In this paper, we study the Cartesian product and its generalization of a directed graph G and a directed cycle. We show that if G has “strong” fault-Hamiltonicity properties, then so does GCn, that is, the Cartesian product of G and a cycle of length n. We also discuss some related problems.