MathOverflow

Return to Question

formatting
Source Link
YCor
YCor
  • 59.4k
  • 5
  • 175
  • 270

Hamiltonian cycles in Cayley graph on Alternatingalternating group

Let $G=Cay(A_n,S)$$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 hamiltonianHamiltonian 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 Alternatingalternating 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.

Hamiltonian cycles in Cayley graph on Alternating group

Let $G=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.

Hamiltonian cycles in Cayley graph on alternating group

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.

added 4 characters in body
Source Link
vidyarthi
vidyarthi
  • 1.8k
  • 1
  • 13
  • 20

Let $G=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.

Let $G=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.

Let $G=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.

Source Link
vidyarthi
vidyarthi
  • 1.8k
  • 1
  • 13
  • 20

Hamiltonian cycles in Cayley graph on Alternating group

Let $G=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.

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.