Paths in groups

Question

Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.

Question: For what groups does there exist a Hamiltonian path in $K(G)$ whose edge labels exhaust the elements of $G$, apart from the identity?

Some observations:

1. If $G={\Bbb Z}/12{\Bbb Z}$, mathematical music theory calls such paths "all-interval rows."

2. No such paths exist for cyclic groups of odd order greater than 1 because the sum of all elements in such a group equals the identity. More generally, when $G$ abelian has such a path, I believe that $G$ must have exactly one factor of even order when expressed as a product of cyclic groups, or equivalently, a unique element of order 2. I don't know the status of the converse.

3. Any Hamiltonian path determines a sequence of $|G|-1$ non-identity edge labels. Heuristically, a random such sequence has probability $(|G|-1)!/ {(|G|-1)}^{|G|-1}$ of having no repeated labels. This predicts that the desired paths exist in great profusion, at least absent any global obstruction as in the previous comment. Where I have made exhaustive searches either no desired paths turned up at all, or I saw a total reasonably consistent with the heuristic. Can one prove or disprove anything along these lines? Even-order cyclic groups have paths of the desired sort, but I don't have any interesting bounds on the total counts even in this case.

4. The case of dihedral times ${\Bbb Z}/2{\Bbb Z}$ has mathematical music theory interest. Paths exist in profusion with the dihedral group factor having order 6, 8, 10, 12 or 24 (the musically most interest case!), but I've yet to see any desired paths searching orders 14, though this might simply reflect the vast size of the search space. (I have now found examples for 24, but only by using an ad hoc hack whose effectiveness I don't understand.)

Answer 1

Groups with this property are known as sequenceable, although the standard definition of a sequenceable group looks a little different: namely, a finite group $G$ is called sequenceable if its elements can be arranged in a sequence $(g_1,\ldots,g_n)$, where $n=|G|$, so that all partial products $a_1:=g_1,\ a_2:=g_1g_2,\ \ldots,\ a_n:=g_1\dotsb g_n$ are pairwise distinct. The link to your property is established by the simple observation that in this case $(a_1,\ldots,a_n)$ is a Hamiltonian path with $a_i^{-1}a_{i+1}$ pairwise distinct, and this is reversible: if $(a_1,\ldots,a_n)$ is a Hamiltonian path with $a_i^{-1}a_{i+1}$ pairwise distinct, then $g_1:=e,\ g_2:=a_1^{-1}a_2,\ \ldots,\ g_n:=a_{n-1}^{-1}a_n$ is an arrangement of the group elements with all partial products pairwise distinct.

Abelian sequenceable groups have been characterized completely. If $(g_1,\ldots,g_n)$ is an arrangement of the elements of a finite abelian group $G$ of order $n$ with all partial products pairwise distinct, then none of $g_2,\ldots,g_n$ can be equal to the neutral element of the group $e$. Hence, $g_1=e$, and therefore $g_1\dotsb g_n\ne e$; that is, the product of all group elements is distinct from the neutral element of the group. It is not difficult to see that an abelian group has this property if and only if it is a group with exactly one involution. Conversely, it was shown by B. Gordon (Sequences in groups with distinct partial products, 1961) that any finite abelian one-involution group is sequenceable. To sum up,

In the case where $G$ is abelian, the necessary and sufficient condition for a Hamiltonian path with the property in question to exist is that $G$ has exactly one involution.

The non-abelian case is subtler, but there are some partial results in this direction, too. For a comprehensive and up-to-date account see a recent paper by Ollis. Related stuff and more references can be found here.