3
$\begingroup$

Let $G=\operatorname{Cay}(A_n,S)$ be the Cayley graph on the Alternating group $A_n\quad n\ge4$ with generating set $S=\{(1,2,3),(1,2,4),\ldots,(1,4,2),(1,3,2)\}$. One Hamiltonian cycle in $G$ for $n=4$ is found as $e-(1,2,3)-(1,3,2)-(1,3,4)-(1,3)(2,4)-(1,2,4)-(2,4,3)-(1,4,3)-(1,2)(3,4)-(2,3,4)-(1,4)(2,3)-(1,4,2)-e$.

The pattern I used to find the Hamiltonian cycle was to multiply successively by $(1,2,3),(1,2,3),(1,2,4),(1,2,4),(1,3,2),(1,3,2),(1,4,2),(1,4,2),(1,3,2),(14,2),(1,2,3),(1,2,4)$.

My question is, is there a similar algorithm for generating Hamiltonian cycle in higher order alternating groups? I also think the graphs can be partitioned into edge-disjoint Hamiltonian cycles (this is true for the case of $A_4$). Is this true? Thanks beforehand.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ It seems to me that all your questions can be answered by H.Su, S.-Y.Chen, S.-S.Kao, (2011). Mutually independent Hamiltonian cycles in alternating group graphs, The Journal of Supercomputing, 61(3), 560-571. $\endgroup$
    – kabenyuk
    Commented Jun 6, 2022 at 15:06
  • $\begingroup$ @kabenyuk As I seethe paper at first glance, it seems the answers are affirmative to my questions. Is this right? $\endgroup$
    – vidyarthi
    Commented Jun 6, 2022 at 17:35
  • $\begingroup$ Can you clarify what is $S$? Is it the set of $3$-cycles? $\endgroup$
    – verret
    Commented Jun 6, 2022 at 18:36
  • $\begingroup$ @vidyarthi Yes, almost so. For every $n\geq3$ in the graph $AG_n$ in this paper, $2n - 4$ mutually independent Hamiltonian cycles are explicitly constructed. Note the definitions. $\endgroup$
    – kabenyuk
    Commented Jun 7, 2022 at 4:28
  • $\begingroup$ @verret yes, it is the set of $3$-cycles $\endgroup$
    – vidyarthi
    Commented Jun 8, 2022 at 11:06

0

Reset to default

You must log in to answer this question.