Fault-Hamiltonicity of Cartesian products of directed cycles

Abstract

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 G □ C_n, that is, the Cartesian product of G and a cycle of length n. We also discuss some related problems.