Consider an undirected Cayley graph of a finite group $\mathbb{Z}_p \times \mathbb{Z}_q$, where $p$ and $q$ are distinct primes. Let the generating set for the Cayley graph be $S=\{g_p, g_q\}$, where $|g_p|=p$ and $|g_q|=q$. Let a Hamiltonian cycle in the Cayley graph be,

$g_p g_p g_q ... g_p g_q=e$ $\,\,\,\rightarrow$ (1)

and suppose it simplifies as,

$g_p^m g_q^n =e \,\,\, \rightarrow$ (2)

Suppose we don't know (1) but only knows $p$ and $q$. Then can we find $m$ and $n$ by taking,

$m \equiv 0 (mod p)$

$n \equiv 0 (mod q)$

such that those $m$ and $n$ represent the relationship relevant to a Hamiltonian cycle?

I mean, as an example if we try to find something like,


$m \equiv 0 (mod p)$

$n \equiv 0 (mod q)$

by imposing a condition "maximum", then will it mean that the $m$ and $n$ values are coming from an equation relevant to a Hamiltonian cycle?

Or is there any other condition which can be mentioned to obtain the $m$ and $n$ values relevant to a Hamiltonian cycle?

If I think of the number of terms in (1), it should be equal to the order of the group, which is $pq$. Then I started to think like if we take the sum of the powers of all the terms, then it should be equal to $pq$ and we will be able to impose a condition as "solve the above two congruence equations such that $m+n=pq$". But this is not really happening since the Cayley graph is an undirected graph, so there can be negative powers (i. e. $g_p^{-1}, g_q^{-1}$) as well and so the values of $m$ and $n$ will not be representing the number of $g_p$ and $g_q$ terms. Hence $m+n \neq pq$.


Your Answer

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

Browse other questions tagged or ask your own question.