In 1978 Trotter and Erdos gave necessary and sufficient conditions for the Cartesian product C_nXC_m of two directed cycles to be Hamiltonian. Namely, C_nXC_m is Hamiltonian if and only if there exist positive integers d_1, and d_2 such that gcd(d_1, n) = 1 = gcd(d_2, m) and d = d_1 + d_2 where d = gcd(m,n). We note that thirty years earlier Rankin implicitly gave necessary and sufficient conditions for the existence of a Hamiltonian cycle in the Cartesian product of two directed cycles, but this result went unnoticed. Several papers, have studied the hamiltonicity of directed graphs obtained from C_nXC_m by adding additional edges. In 1983 Penn and Witte gave necessary and sufficient conditions for C_nXC_m to be hypo-Hamiltonian. A digraph D is said to be hypo-Hamiltonian if D is not Hamiltonian but every vertex deleted subdigraph D - {v} is Hamiltonian. Namely C_nXC_m is hypo-Hamiltonian if and only if there exist relatively prime positive integers s and t such that sn + tm = nm - 1. More recently, Barone, Mauntel, and Miller [1] gave necessary and sufficient conditions for C_nXC_m - C_xXC_y, the Cartesian product of two directed cycles minus a subgroup to be Hamiltonian. In [4] the authors investigated hamiltonicity in the digraphs C_nXC_m-RT_k (and C_nXC_m-LT_k). These digraphs are obtained from C_nXC_m by removing T_k vertices in a triangular pattern from the upper right corner (upper left corner) of directed graph C_nXC_m and then reconnecting the cycles, where T_k is the k~(th) triangular number. In [5] the authors investigated hamiltonicity in the digraphs C_nXC_m-S_k. These digraphs are obtained from C_nXC_m by removing S_k vertices in a square pattern from the upper right corner of directed graph C_nXC_m and then reconnecting the cycles, where S_k is the k~(th) triangular number. In this paper we continue to study the hamiltonicity of C_nXC_m-S_k.
展开▼
