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
    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
    Jun 6, 2022 at 17:35
  • $\begingroup$ Can you clarify what is $S$? Is it the set of $3$-cycles? $\endgroup$
    – verret
    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
    Jun 7, 2022 at 4:28
  • $\begingroup$ @verret yes, it is the set of $3$-cycles $\endgroup$
    – vidyarthi
    Jun 8, 2022 at 11:06

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.