On Cayley Digraphs That Do Not Have Hamiltonian Paths

We construct an infinite family of connected, -generated Cayley digraphs that do not have hamiltonian paths, such that the orders of the generators and are unbounded. We also prove that if is any finite group with , then every connected Cayley digraph on has a hamiltonian path (but the conclusion does not always hold when or ). 1. Introduction Definition 1. For a subset of a finite group , the Cayley digraph？？ is the directed graph whose vertices are the elements of and with a directed edge for every and . The corresponding Cayley graph is the underlying undirected graph that is obtained by removing the orientations from all the directed edges. It has been conjectured that every (nontrivial) connected Cayley graph has a hamiltonian cycle. (See the bibliography of [1] for some of the literature on this problem.) This conjecture does not extend to the directed case, because there are many examples of connected Cayley digraphs that do not have hamiltonian cycles. In fact, infinitely many Cayley digraphs do not even have a hamiltonian path. Proposition 2 (attributed to Milnor [2, p. 201]). Assume the finite group is generated by two elements and , such that . If , then the Cayley digraph does not have a hamiltonian path. The examples in the above proposition are very constrained, because the order of one generator must be exactly 2 and the order of the other generator must be exactly 3. In this note, we provide an infinite family of examples in which the orders of the generators are not restricted in this way. In fact, and can both be of arbitrarily large order. Theorem 3. For any , there is a connected Cayley digraph , such that(1) does not have a hamiltonian path,(2) and both have order greater than .Furthermore, if is any prime number such that and , then we may construct the example so that the commutator subgroup of has order . More precisely, is a semidirect product of two cyclic groups, so is metacyclic. Remark 4. Here are some related open questions and other comments.(1)The above results show that connected Cayley digraphs on solvable groups do not always have hamiltonian paths. On the other hand, it is an open question whether connected Cayley digraphs on nilpotent groups always have hamiltonian paths. (See [3] for recent results on the nilpotent case.)(2)The above results always produce a digraph with an even number of vertices. Do there exist infinitely many connected Cayley digraphs of odd order that do not have hamiltonian paths?(3)We conjecture that the assumption “ (mod？4)” can be eliminated from the statement of Theorem 3. On the other