ISSN 2148-838X J. Algebra Comb. Discrete Appl. 10(1) • 61–71 Received: 9 April 2022 Accepted: 9 July 2022 Journal of Algebra Combinatorics Discrete Structures and Applications Hamiltonicity after reversing the directed edges at a vertex of a Cartesian product Research Article Dave Witte Morris Abstract: Let ~Cm and ~Cn be directed cycles of length m and n, with m, n ≥ 3, and let P( ~Cm � ~Cn) be the digraph that is obtained from the Cartesian product ~Cm� ~Cn by choosing a vertex v, and reversing the orientation of all four directed edges that are incident with v. (This operation is called “pushing” at the vertex v.) By applying a special case of unpublished work of S. X. Wu, we find elementary number- theoretic necessary and sufficient conditions for the existence of a hamiltonian cycle in P( ~Cm � ~Cn). A consequence is that if P( ~Cm � ~Cn) is hamiltonian, then gcd(m, n) = 1, which implies that ~Cm � ~Cn is not hamiltonian. This final conclusion verifies a conjecture of J. B. Klerlein and E. C. Carr. 2010 MSC: 05C45, 05C20, 05C76 Keywords: Hamiltonian cycle, Cartesian product, Directed cycle, Pushing at a vertex, Reverse edges 1. Preliminaries Notation 1.1. For m, n, i, j ∈ Z (with m 6= 0 and n 6= 0), we define the integer am,n(i, j) by the following conditions: am,n(i, j) ≡ i (mod m), am,n(i, j) ≡ j (mod n), and 1 ≤ am,n(i, j) ≤ lcm(m, n). The integer is unique, if it exists. By the Chinese Remainder Theorem, am,n(i, j) does exist whenever gcd(m, n) = 1 (or, more generally, whenever i ≡ j (mod gcd(m, n))). Notation 1.2. We use ~Cm to denote a directed cycle of length m. Definition 1.3 ([6, p. 88]). If X is a digraph that is vertex-transitive, then the digraph P(X) is con- structed from X by choosing a vertex v, and reversing the orientation of each directed edge that is incident with v. (This operation is called “pushing” at the vertex v [6, 7].) Since X is vertex-transitive, the isomorphism class of the resulting digraph is independent of the choice of v. Dave Witte Morris; Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, T1K 6R4, Canada (dmorris@deductivepress.ca). 61 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 Definition 1.4 ([4, pp. 35 and 421]). Recall that the Cartesian product X �Y of two digraphs X and Y is the digraph whose vertex set is V (X)×V (Y ), with a directed edge from (x1, y1) to (x2, y2) if and only if either • x1 = x2, and there is a directed edge from y1 to y2 in Y , or • y1 = y2, and there is a directed edge from x1 to x2 in X. 2. Statement of the main result This note explains that a special case of unpublished work of S. X. Wu [11] (or slightly later published work of S. J. Curran et al. [1]) provides the following elementary number-theoretic necessary and sufficient conditions for P(~Cm � ~Cn) to be hamiltonian. Proposition 2.1. Let ~Cm and ~Cn be directed cycles of length ≥ 3. The digraph P(~Cm � ~Cn) has a hamiltonian cycle if and only if (1) gcd(m, n) = 1, (2) min{am,n(0,−2), am,n(−2, 0)} < min { am,n(0,−1), am,n(−1, 0) } , and (3) gcd ( am,n(0,−4) m , am,n(−4, 0) n ) = 1. If gcd(m, n) = 1, then it is well known (and easy to see) that ~Cm � ~Cn is not hamiltonian [3, Thm. 28.1, p. 510]. Therefore, the proposition has the following consequence, which was conjectured by J. B. Klerlein and E. C. Carr [6, p. 94]: Corollary 2.2. If ~Cm � ~Cn is hamiltonian (and m, n ≥ 3), then P(~Cm � ~Cn) is not hamiltonian. Remarks 2.3. (1) Proposition 2.1 requires m and n to be at least 3. The remaining case was settled by J. B. Klerlein and E. C. Carr [6, Thm. 6]: P(~C2 � ~Cn) is hamiltonian if and only if n ∈ {2, 3}. (Since ~C2 � ~C2 and P(~C2 � ~C2) are hamiltonian, it is clear that corollary 2.2 would be false if it allowed the case where m = n = 2.) (2) J. B. Klerlein and E. C. Carr also determined whether P(Cm � Cn) is hamiltonian in certain other special cases. In particular, they [6, Thm. 7] proved a much more concrete form of the case m = 3 of proposition 2.1: P(C3 � Cn) is hamiltonian if and only if n ≡ 2 (mod 3). (3) The conditions in proposition 2.1 are so efficient that they can be checked by a computer in seconds, even if m and n have 100,000 digits. This can be verified by using the sample code in Fig. 1. 3. Proof of the main result We assume that the vertices of ~Cm � ~Cn are identified in the natural way with the elements of the abelian group Zm ×Zn. Notation 3.1 (cf. [11, p. 2]). (1) For a, b ∈ Z+, the rectangle Ra,b is the subset {0, 1, . . . , a−1}×{0, 1, . . . , b−1} of V (~Cm � ~Cn). 62 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 def is_PCmxCn_hamiltonian(m, n): r"""Return ‘True‘ if ‘P(C_m x C_n)‘ has a hamiltonian cycle (otherwise return ‘False‘).""" m = Integer(m) n = Integer(n) if min(m, n) < 3: raise NotImplementedError("m and n must be at least 3") if gcd(m, n) != 1: return False def a(i, j): return crt(i, j, m, n) if min( a(0, -2), a(-2, 0) ) > min( a(0, -1), a(-1, 0) ): return False return gcd( a(0, -4) // m, a(-4, 0) // n ) == 1 Figure 1. A sagemath program that implements proposition 2.1. (This program can be run online at https://cocalc.com.) For example, is_PCmxCn_hamiltonian(3,5) returns True because the digraph P( ~C3 � ~C5) is hamiltonian (see Remarks 2.3(2)). (2) We use (~Cm � ~Cn) r Ra,b to denote the digraph that is obtained from ~Cm � ~Cn by deleting all of the vertices in Ra,b (and also deleting all of the directed edges that are incident with this set). The following simple observation is crucial: Lemma 3.2. For m, n ≥ 3, the digraph P(~Cm � ~Cn) is hamiltonian if and only if (~Cm � ~Cn) r R2,2 is hamiltonian. Proof. (⇒) Figure 2(a) shows a part of P(~Cm � ~Cn) with the pushed vertex v at its centre. (All nine vertices in the figure are distinct, because m, n ≥ 3.) Note that the vertices v + (1, 0) and v + (0, 1) have only one in-edge, and the vertices v − (1, 0) and v − (0, 1) have only one out-edge. This implies that the hamiltonian cycle must traverse these four directed edges (which are dark in the figure). The out-edges of v go to v − (1, 0) and v − (0, 1). By symmetry (i.e., by interchanging m and n if necessary), we may assume without loss of generality that the hamiltonian cycle uses the (white) directed edge from v to v − (1, 0). Then the hamiltonian cycle cannot use the edge from v + (0, 1) to v (because that would create a 4-cycle), so it must use the other in-edge of v, which is the (grey) directed edge from v + (1, 0) to v. Also, the hamiltonian cycle cannot use the (striped) directed edge from v−(1, 1) to v − (1, 0) (because it already uses a different in-edge of v − (1, 0)), so it must use the other out-edge of v − (1, 1), which goes to v − (0, 1) (and is grey in the figure). Now, assuming without loss of generality that R2,2 consists of the four white vertices in the bottom right of the picture, we can construct a hamiltonian cycle in (~Cm � ~Cn) r R2,2 by deleting the edges in the walk v − (1, 1), v − (0, 1), v + (1,−1), v + (1, 0), v, v − (1, 0), and inserting the (striped) directed edge from v − (1, 1) to v − (1, 0). (⇐) Figure 2(b) shows the same portion of P(~Cm � ~Cn), centred at the pushed vertex v, with the (white) vertices of the rectangle R2,2 in the bottom right corner again. Note that P(~Cm � ~Cn) r R2,2 = (~Cm � ~Cn) r R2,2, so, by assumption, there is a hamiltonian cycle in P(~Cm � ~Cn) r R2,2. It must use all of the directed edges that are dark or striped in this picture, because v − (1, 1) and v − (1, 0) have only one out-edge 63 https://cocalc.com Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 v (a) v (b) Figure 2. Two drawings centred at the pushed vertex v. that has not been deleted, and the vertices v + (0, 1) and v + (1, 1) have only one in-edge that has not been deleted. Then we can construct a hamiltonian cycle in P(~Cm � ~Cn) by reversing the process in the previous part of the proof: delete the (striped) edge from v − (1, 1) to v − (1, 0), and replace it with the walk v − (1, 1), v − (0, 1), v + (1,−1), v + (1, 0), v, v − (1, 0), whose edges are grey in the picture. Hence, the existence of a hamiltonian cycle in P(~Cm � ~Cn) is characterized by the case a = b = 2 of the following result: Theorem 3.3 (S. X. Wu [11, Cor. 11]). The digraph (~Cm � ~Cn) r Ra,b is hamiltonian if and only if either the following conditions are satisfied, or they are satisfied after interchanging m and n, and also interchanging a and b: am,n(−a, 0) exists, am,n(−a, 0) = min { am,n(−a,−b), am,n(−a,−b + 1), am,n(−a,−b + 2), . . . , am,n(−a, 0), am,n(−a,−b), am,n(−a + 1,−b), am,n(−a + 2,−b), . . . , am,n(0,−b) } (where any terms in the minimum that do not exist are simply ignored), and gcd ( n− b− b ⌊ am,n(−a, 0) m ⌋ , b am,n(−a, 0) n ) = 1. Remarks 3.4. (1) S. X. Wu showed that if (~Cm � ~Cn) r Ra,b has a hamiltonian cycle, then it is unique (see lemma 5.4 below). It follows that if P(~Cm � ~Cn) is hamiltonian (and m, n ≥ 3), then P(~Cm � ~Cn) has exactly two hamiltonian cycles. One hamiltonian cycle will be constructed in the proof of lemma 3.2, and the other is constructed by interchanging ~Cm and ~Cn in this proof (or, in other words, by reflecting Fig. 2(b) across the line y = x). (2) A very different formulation of the conditions in the statement of Theorem 3.3 was proved by S. J. Curran et al. [1, Thm. 4.3], as a special case of a more general version [1, Thm. 4.2] that applies to all 2-generated Cayley digraphs on finite abelian groups, not only Cartesian products of directed cycles. We need only the special case where a = b = 2, which can be restated as follows (see Section 4 or Section 5): 64 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 Corollary 3.5. For m, n ≥ 3, the digraph (~Cm � ~Cn) r R2,2 is hamiltonian if and only if: (1) gcd(m, n) = 1, (2) min{am,n(0,−2), am,n(−2, 0)} < min { am,n(0,−1), am,n(−1, 0) } , and (3) gcd ( am,n(0,−4) m , am,n(−4, 0) n ) = 1. Proof of proposition 2.1. Combine lemma 3.2 and corollary 3.5. 4. Proof of the corollary 3.5 from the theorem 3.3 We now explain how to derive corollary 3.5 from Theorem 3.3. (Alternatively, the corollary could also be derived from the work of S. J. Curran et al. [1, Thm. 4.3], or see Section 5 for a direct proof that does not assume familiarity with [1] or [11].) Actually, we prove only (⇒) in this section, but the argument is reversible. The conclusions of the corollary are symmetric under interchanging m and n, so we may assume that the conditions in the statement of Theorem 3.3 hold. For a = b = 2, this means: am,n(−2, 0) = min { am,n(−2,−2), am,n(−2,−1), am,n(−2, 0), am,n(−2,−2), am,n(−1,−2), am,n(0,−2) } (1) and gcd ( n−2−2 ⌊ am,n(−2, 0) m ⌋ , 2 am,n(−2, 0) n ) = 1. (2) (1) Note that n must be odd. (Otherwise, both terms in the gcd of (2) are even, which contradicts the fact that the gcd is 1.) Also, since am,n(−2, 0) exists, we know that gcd(m, n) ∈ {1, 2}. From the fact that n is odd, we conclude that gcd(m, n) = 1. (2) Since am,n(i−1, j −1) = am,n(i, j)−1 (unless i ≡ j ≡ 0 (mod lcm(m, n))), (3) we have am,n(−2,−1) = am,n(−1, 0)−1 and am,n(−1,−2) = am,n(0,−1)−1. (4) Therefore, we see from (1) that (2) holds. (For reversing the argument, note that am,n(−2,−2) = mn−2, so it is always true that am,n(−2, 0) < am,n(−2,−2), and also note that the inequality am,n(−2, 0) < am,n(0,−2) can be achieved by interchang- ing m and n if it does not already hold.) (3) Note that am,n(−2, 0) + am,n(0,−2) = mn−2, because the left-hand side is congruent to −2 modulo both m and n (and we know from (1) that m and n are relatively prime). Since (by (1)) we have am,n(−2, 0) < am,n(0,−2), this implies that am,n(−2, 0) < mn 2 −1, 65 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 so am,n(−4, 0) = 2 am,n(−2, 0). Therefore, we have 2 am,n(−2, 0) n = am,n(−4, 0) n . Hence, in order to establish that (2) is the same as conclusion (3) of the corollary, all that remains is to show n−2−2 ⌊ am,n(−2, 0) m ⌋ = am,n(0,−4) m . Since am,n(−2, 0) + 2 is a multiple of m, we see that the left-hand side is n−2−2 ( am,n(−2, 0) + 2 m −1 ) = n−2 am,n(−2, 0) + 2 m = mn−2 am,n(−2, 0)−4 m . Also note that mn−2 am,n(−2, 0)−4 > mn−2 (mn 2 −1 ) −4 = −2. It is therefore easy to see that mn−2 am,n(−2, 0)−4 = am,n(0,−4) (because the two sides are congruent modulo both m and n), which completes the proof. 5. Direct proof of the corollary 3.5 For completeness (since [11] was never published), and because some readers may find it instructive, we sketch a direct proof of corollary 3.5 that is based on S. X. Wu’s proof [11, §4] of Theorem 3.3. (The same ideas apply to the general case of Theorem 3.3, but the details are more complicated.) We begin with two definitions and some lemmas. Definition 5.1 ([9]). A spanning subdigraph H of a digraph X is a vertex-disjoint cycle cover if H is a vertex-disjoint union of directed cycles. (Equivalently, the invalence and outvalence of every vertex of H is 1.) Definition 5.2 (cf. [5, p. 82]). Assume H is a vertex-disjoint cycle cover of (~Cm � ~Cn) r R2,2. Let v be a vertex of H, and let s ∈ {(1, 0), (0, 1)}. We say that v travels by s if the out-edge of v is the directed edge from v to v + s. The arguments in this section utilize basic properties of the “arc-forcing subgroup” 〈(1,−1)〉 [10, §2.3] that were discovered by R. A. Rankin [8, Lem. 1] and D. Housman [5, pp. 82–83]. The specific facts that we need are recorded in the following lemma. Lemma 5.3 (cf. [11, p. 2] or [1, Rem. 2.2]). Let H be a vertex-disjoint cycle cover of (~Cm � ~Cn) r R2,2. For every vertex v of H: (1) If v travels by (1, 0), and v + (1,−1) /∈ R2,2, then v + (1,−1) also travels by (1, 0). (2) If v travels by (1, 0), and neither v − (1,−1) nor v + (0, 1) is in R2,2, then v − (1,−1) also travels by (1, 0). 66 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 (3) If v travels by (0, 1), and v − (1,−1) /∈ R2,2, then v − (1,−1) also travels by (0, 1). (4) If v travels by (0, 1), and neither v + (1,−1) nor v + (1, 0) is in R2,2, then v + (1,−1) also travels by (0, 1). Proof. (1, 3) By symmetry, it suffices to prove (1). For convenience, let w = v + (1, 0). Since H is a vertex-disjoint cycle cover, we know that H cannot have both a directed edge from v to w and a directed edge from v + (1,−1) to w (because the invalence of w cannot be greater than 1). Hence, v + (1,−1) cannot travel by (0, 1). However, v+(1,−1) is a vertex of H (because, by assumption, it is not in R2,2), so it must have some out-edge. We conclude that it travels by (1, 0), since that is the only other possibility. (2, 4) By symmetry, it suffices to prove (2). For convenience, let w = v + (0, 1). Since v travels by (1, 0), it does not travel by (0, 1), so H does not contain the directed edge from v to w. Since w must have an in-edge, this implies that H has the directed edge from v − (1,−1) to w (since that is the only other possibility). This means that v − (1,−1) travels by (1, 0). Lemma 5.4 (Wu [11, Lem. 1] or [1, Lem. 2.3]). For m, n ≥ 2, the digraph (~Cm � ~Cn)rR2,2 has no more than one vertex-disjoint cycle cover. Proof. Let H be a vertex-disjoint cycle cover. We claim that every coset of the subgroup 〈(1,−1)〉 contains at least one element of R2,2. Suppose not, so we may let v + 〈(1,−1)〉 be a coset that does not intersect the set R2,2. By symmetry, we may assume, without loss of generality, that v travels by (1, 0). Then, by repeated application of lemma 5.3(1), we conclude that every element of this coset travels by (1, 0). Since the terminal endpoint of every directed edge of H must be a vertex of H, this implies that every element of the coset v + (1, 0) + 〈(1,−1)〉 is a vertex of H. In other words, this coset does not intersect the set R2,2. By repeating this argument, we conclude, for every k ∈ Z+, that the coset v + (k, 0) + 〈(1,−1)〉 does not intersect R2,2. However, the union of these cosets is all of ~Cm � ~Cn. We conclude that R2,2 has no elements, which is a contradiction. The claim implies that every vertex of H is contained in set of the form Iv,k = {v, v + (1,−1), v + 2(1,−1), . . . , v + k(1,−1)}, such that (a) either v − (1,−1) ∈ R2,2 or v + (0, 1) ∈ R2,2, (b) either v + (k + 1) (1,−1) ∈ R2,2 or v + (k + 1) + (1, 0) ∈ R2,2, but (c) no element of Iv,k is in R2,2, and (d) for 1 ≤ j < k, neither v + j(1,−1) + (1, 0) nor v + j(1,−1) + (1, 0) is in R2,2. From (c) and (d) (combined with lemma 5.3) and induction, we see that either every element of Iv,k travels by (1, 0), or every element of Iv,k travels by (0, 1). To complete the proof, we will show that there is no choice about whether these vertices travel by (1, 0) or by (1, 0): it is uniquely determined for each v. First of all, if v + (0, 1) ∈ R2,2, then v cannot travel by (0, 1), so it must travel by (1, 0); hence, every vertex in Iv,k must travel by (0, 1). On the other hand, if v + (0, 1) /∈ R2,2, then (by (a)) we must have v − (1,−1) ∈ R2,2, so the vertex v − (1,−1) is not in H, and therefore cannot travel by (1, 0). Since v + (0, 1) must have an in-edge, we conclude that v travels by (0, 1); hence, every vertex in Iv,k must travel by (0, 1). 67 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 Lemma 5.5 (cf. [11, Thm. 10]). For m, n ≥ 3, the digraph (~Cm � ~Cn) r R2,2 has a vertex-disjoint cycle cover if and only if am,n(−2, 0) and am,n(0,−2) exist, and min { am,n(−2, 0), am,n(0,−2) } < min { am,n(0,−1), am,n(−1, 0) } . Furthermore, if the digraph does have a vertex-disjoint cycle cover, then the number of vertices that travel by (1, 0) in this subdigraph is exactly twice the left-hand side of the above inequality. Proof. (⇒) If a vertex u travels by (1, 0), and we let r(u) = min{k ∈ Z+ | u + k(1,−1) ∈ R2,2 }, (5) then it follows from lemma 5.3(1) (and induction on k) that u+k(1,−1) travels by (1, 0) for 0 ≤ k < r(u). This implies u + k(1,−1) + (1, 0) /∈ R2,2 for 0 ≤ k < r(u). In particular, we can apply this with u = (1,−1), since this vertex travels by (1, 0) because u+(0, 1) = (1, 0) ∈ R2,2. We have R2,2 = { (0, 1), (1, 1), (0, 0), (1, 0) } = { (1,−1) + (−1, 2), (1,−1) + (0, 2), (1,−1) + (−1, 1), (1,−1) + (0, 1) } (6) = { u + am,n(−1,−2) · (1,−1), u + am,n(0,−2) · (1,−1), u + am,n(−1,−1) · (1,−1), u + am,n(0,−1) · (1,−1) } , so r(u) = min{am,n(−1,−2), am,n(0,−2), am,n(−1,−1), am,n(0,−1)}. (7) Also, since u + am,n(−2,−1) · (1,−1) + (1, 0) = (1,−1) + (−2, 1) + (1, 0) = (0, 0) ∈ R2,2 and u + am,n(−2,−2) · (1,−1) + (1, 0) = (1,−1) + (−2, 2) + (1, 0) = (0, 1) ∈ R2,2, we know that u + am,n(−2,−1) · (1,−1) and u + am,n(−2,−2) · (1,−1) do not travel by (1, 0), so r(u) ≤ min { am,n(−2,−1), am,n(−2,−2)}. (8) Since am,n(−2,−2) = lcm(m, n)−2 is very large, it is almost entirely irrelevant in (8), but it does imply that am,n(−1,−1) = lcm(m, n) − 1 is not the only term that exists in the right-hand side of (7). This implies that gcd(m, n) ∈{1, 2}, so am,n(−2, 0) and am,n(0,−2) exist. We may now assume that am,n(0,−1) and (equivalently) am,n(−1, 0) exist, for otherwise the inequal- ity in the statement of the lemma is vacuously true. We may also assume (by interchanging m and n if necessary) that min { am,n(0,−1), am,n(−1, 0) } = am,n(−1, 0). Thus, we see from (4) that (8) is equivalent to the condition that am,n(0,−2) < am,n(−1, 0). This establishes the inequality in the statement of the lemma. (⇐) Let u = (1,−1) and assume, without loss of generality, that am,n(−1, 0) < am,n(0,−1). 68 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 Since am,n(−1, 0) + am,n(0,−1) = am,n(−1,−1) = lcm(m, n)−1, this implies that am,n(−1, 0) < lcm(m, n)/2, so am,n(−2, 0) = 2 am,n(−1, 0) > am,n(−1, 0). So we see from the assumption of this direction of the proof that am,n(0,−2) < am,n(−1, 0) = min { am,n(−1, 0), am,n(0,−1), am,n(−2, 0) } . (9) We then conclude from (6) (and the definition of r(u) in (5)) that r(u) = am,n(0,−2) (10) and (using (3)) that u + k(1,−1) + (1, 0) /∈ R2,2 for 0 ≤ k < r(u). Let u′ = u− (1, 0) = (0,−1). We claim that r(u′) = r(u). (11) To see this, first note that u′ + r(u) · (1,−1) = (0,−1) + am,n(0,−2) · (1,−1) = (0,−1) + (0, 2) = (0, 1) ∈ R2,2, so r(u′) ≤ r(u). On the other hand, we have R2,2 = { (0, 1), (1, 1), (0, 0), (1, 0) } = { (0,−1) + (0, 2), (0,−1) + (1, 2), (0,−1) + (0, 1), (0,−1) + (1, 1) } = { u′ + am,n(0,−2) · (1,−1), u′ + am,n(1,−2) · (1,−1), u′ + am,n(0,−1) · (1,−1), u′ + am,n(1,−1) · (1,−1) } , so r(u′) = min { am,n(0,−2), am,n(1,−2), am,n(0,−1), am,n(1,−1) } = min { am,n(0,−2), am,n(0,−3) + 1, am,n(0,−1), am,n(0,−2) + 1 } From (9), we know that the only value in this minimum that could possibly be smaller than r(u) = am,n(0,−2) is am,n(0,−3) + 1. However, we have am,n(0,−2) + am,n(0,−1) < am,n(−1, 0) + am,n(0,−1) = lcm(m, n)−1 < lcm(m, n), so am,n(0,−3) = am,n(0,−2) + am,n(0,−1) > am,n(0,−2) = r(u). This completes the proof of the claim. Note that, for 0 ≤ k < r(u), we have u′ + k(1,−1) + (1, 0) = u + k(1,−1) /∈ R2,2. Also note that u and u′ are the only vertices in (~Cm � ~Cn) r R2,2 that cannot travel by (0, 1). Therefore, we can construct a spanning subdigraph H in which a vertex travels by (1, 0) if it is in the set{ v + k(1,−1) ∣∣∣∣ v ∈{u, u′},0 ≤ k < r(u) } 69 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 and travels by (0, 1) otherwise. By construction (and (11)), if a vertex v travels by (1, 0), and v+(1,−1) /∈ R2,2, then v + (1,−1) also travels by (1, 0). Hence, no vertex has invalence 2, so the in-degree (and out- degree) of every vertex of H is 1, which means that H is the desired vertex-disjoint cycle cover. Furthermore, we know from the construction of H (together with (9) and (10)) that the number of vertices that travel by (1, 0) is as specified in the final sentence of the statement of the lemma. Since H is the only vertex-disjoint cycle cover (see lemma 5.4), this completes the proof. Direct proof of corollary 3.5. Lemma 5.5 provides necessary conditions for the existence of a hamil- tonian cycle (in particular, 2.1(2) must hold), but they is not sufficient, because we need an additional condition that determines whether the cycle cover is a single cycle, rather than a union of several cycles. This condition is provided by the “knot class,” which is a topological concept that was introduced into the study of Cartesian products of directed cycles by S. J. Curran [2, §4]. Namely, let H be the vertex-disjoint cycle cover, and suppose the number of vertices of H that travel by (1, 0) is x, and the number that travel by (0, 1) is y. Then x/m and y/n are integers, and the knot class of H is defined to be the ordered pair (x/m, y/n) [2, Rem. 4.5]. The theory [2, Prop. 4.12(a)] tells us that H consists of a single cycle if and only if gcd(x/m, y/n) = 1. (12) We now use (12) to show that 2.1(1) is a necessary condition for H to be a hamiltonian cycle. The key is to notice that if gcd(m, n) 6= 1, then since lemma 5.5 tells us that am,n(−2, 0) exists, we must have gcd(m, n) = 2, so m and n are even. However, if we assume, without loss of generality, that am,n(0,−2) < am,n(−2, 0), then the last sentence of lemma 5.5 tells us that x = 2 am,n(0,−2). Since the number of vertices of H is mn−4, this implies y = mn−4−x = mn−4−2 am,n(0,−2) = mn−2 am,n(2, 0). Since m is even, it is now obvious that x m = 2 am,n(0,−2) m and y n = m−2 am,n(2, 0) n are even. Hence, gcd(x/m, y/n) 6= 1, so we see from (12) H is not a hamiltonian cycle. To complete the proof, we now consider the situation where 2.1(1) holds, which means that gcd(m, n) = 1. Since x/m and y/n are integers, we know that x ≡ 0 (mod m) and y ≡ 0 (mod n). Also, since the number of vertices of H is mn−4, we know that x + y = mn−4 ≡−4 (mod mn). Combining these congruences tells us that x ≡−4 (mod n) and y ≡−4 (mod m). So x = am,n(0,−4) and y = am,n(−4, 0). We conclude from (12) that H consists of a single cycle (and is therefore a hamiltonian cycle) if and only if the condition in 2.1(3) holds. 70 Dave Witte Morris / J. Algebra Comb. Discrete Appl. 10(1) (2023) 61–71 References [1] S. J. Curran, M. N. Ferencak, C. J. Morgan, J. W. Thompson, The hamiltonicity of a Cayley digraph of a modified abelian group on two generators, Congr. Numerantium 188 (2007) 75–95. [2] S. J. Curran, D. Witte, Hamilton paths in Cartesian products of directed cycles, Cycles in Graphs, edited by B.R. Alspach and C.D. Godsil, North-Holland Publishing Co. 115 (1985) 35–74. [3] J. Gallian, Contemporary Abstract Algebra, 10th ed. CRC Press, Boca Raton, FL (2021). [4] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, 2nd ed. CRC Press, Boca Raton, FL (2011). [5] S.Housman, Enumeration of Hamiltonian paths in Cayley diagrams, Aequationes Math. 23 (1981) 80–97. [6] J.B. Klerlein, E. C. Carr, Hamiltonicity in Cn × Cm after a single push, Congr. Numerantium 190 (2008) 87–96. [7] W. F. Klostermeyer, Pushing vertices and orienting edges, Ars Combin. 51 (1999) 65–75. [8] R .Rankin, A campanological problem in group theory, Proc. Cambridge Philos. Soc. 44 (1948) 17–25. [9] Wikipedia, Vertex cycle cover, (2022, November 19). [10] D. Witte, J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51 (1984) 293–304. [11] S. X. Wu, Cycles in the Cartesian product of two directed cycles, 2007 JMM2007. 71 https://mathscinet.ams.org/mathscinet-getitem?mr=2408756 https://mathscinet.ams.org/mathscinet-getitem?mr=2408756 https://doi.org/10.1016/S0304-0208(08)72996-7 https://doi.org/10.1016/S0304-0208(08)72996-7 https://doi.org/10.1201/9781003142331 https://doi.org/10.1201/b10959 https://doi.org/10.1201/b10959 https://doi.org/10.1007/BF02188014 https://doi.org/10.1007/BF02188014 https://mathscinet.ams.org/mathscinet-getitem?mr=2489794 https://mathscinet.ams.org/mathscinet-getitem?mr=2489794 https://zbmath.org/?q=an:0977.05057 https://doi.org/10.1017/S030500410002394X https://doi.org/10.1017/S030500410002394X https://en.wikipedia.org/wiki/Vertex_cycle_cover https://doi.org/10.1016/0012-365X(84)90010-4 https://doi.org/10.1016/0012-365X(84)90010-4 https://www.jointmathematicsmeetings.org/meetings/national/jmm/1023-05-790.pdf Preliminaries Statement of the main result Proof of the main result Proof of the corollary 3.5 from the theorem 3.3 Direct proof of the corollary 3.5 References