Consider the Cayley graphs $A'G_n$ on the alternating group $A_n$ with generating set $S = \{(1i2) : 3 \leq i \leq n\}$, for $n \geq 4$.

See the following page on Alternating Group Graphs for information on the undirected versions, $AG_n$: Alternating Group Graph. It is known that the $AG_n$ is Hamiltonian for all $n\geq3$.

I suspect that $A'G_n$ is not Hamiltonian, for all $n \geq 4$. It certainly isn't for $n = 4$, which I simply checked by hand.

These graphs, were they to be non-Hamiltonian for all $n \geq 3$, would give a nice infinite family of counterexamples to show that the Lovász Conjecture doesn't hold for Cayley digraphs. According to the linked Wikipedia page, various counterexamples were found by R.A. Rankin, although no mention is made as to what those counterexamples are.

So the question is, is $A'G_n$ Hamiltonian?


If I understood and coded correctly and sage didn't lie $A'G_4$ is not hamiltonian while $A'G_5$ is hamiltonian.

Aded According to sage $A'G_6$ is hamiltonian.

sage code:

def dicaygen(G,ge):
    cayley digraph on gens $ge$
    ve=[i for i in G]
    for i in xrange(len(ve)):
        for j in xrange(len(ve)):
            if i==j:  continue

            if a*b^(-1)in ge:
                ed += [(a,b)]
    return G

sage: n=4;an=AlternatingGroup(n);ge=[an([(1,k,2)]) for k in [ 3 .. n]];g=dicaygen(an,ge);g.is_hamiltonian()
sage: n=5;an=AlternatingGroup(n);ge=[an([(1,k,2)]) for k in [ 3 .. n]];g=dicaygen(an,ge);g.is_hamiltonian()
  • $\begingroup$ I can confirm that the n=5 case is hamiltonian. $\endgroup$ – Gordon Royle Mar 26 '14 at 8:23
  • $\begingroup$ @GordonRoyle Thanks. Sage is slow for larger digraphs. Is there other software for HC in digraphs? $\endgroup$ – joro Mar 26 '14 at 8:31
  • 2
    $\begingroup$ @Gordon: Any moment now you will open your own book and report the simpler example of nonhamiltonian Cayley digraphs of the symmetric group that appears there... $\endgroup$ – Brendan McKay Mar 26 '14 at 10:36
  • 1
    $\begingroup$ @brendan, I did realise that, but it didn't answer the actual question. But to make everyone happy, I'll say that the Cayley (di)graph with generators (1,2) and (1,2,...n) is non hamiltonian if n is even. $\endgroup$ – Gordon Royle Mar 26 '14 at 23:18
  • $\begingroup$ @joro No, I don't know any special software. HC is difficult, though Brendan has some nice heuristics that probably apply to directed graphs as well. $\endgroup$ – Gordon Royle Mar 27 '14 at 1:38

The answer to this question turns out to be already known, and can be found in the following paper: Cayley digraphs and (1,j,n)-sequencings of the alternating groups An.

As it turns out (Assuming I'm not misunderstanding the paper), $A'G_n$ is Hamiltonian for all $n \geq 3$, except when $n = 4$. (Which I didn't expect to be the answer.)

Thanks for your comments, they were very helpful!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.