7
$\begingroup$

Background: A tantalizing conjecture of Lovasz is the following:

Let $G$ be a (finite) connected vertex-transitive graph. Then $G$ contains a Hamiltonian cycle or is one of $5$ counter-examples.

(technically, Lovasz conjectured something about finding Hamiltonian paths in such $G$, but this strengthening has been raised in later literature)

On the Wikipedia article for this conjecture, it is said that it is still open whether all connected Cayley graphs of dihedral groups contain Hamiltonian cycles, but it is known for special cases of generating sets. No reference is given for what "special cases" are known, so I'm curious if the following is open.

Question:

Let $D$ be a (finite) dihedral group, and let $H\le D$ be its subgroup of rotations. Suppose $S\subset D\setminus H$ generates $D$. Does the Cayley graph $\Gamma(D,S)$ have a Hamiltonian cycle?

I think this special case is nice, because with a bit of clever relabelling, one can show that our Cayley graph $\Gamma$ is closely related to a weakly-connected directed Cayley graph $\Gamma'$ defined over $H$, which allows us to conclude that $\Gamma$ has a Hamiltonian path due to the fact that $\Gamma'$ has a directed Hamiltonian path.

$\endgroup$

1 Answer 1

6
$\begingroup$

It turned out to be such a long commentary. Here is what is known about Hamiltonian cycles of dihedral groups:

  1. Conjecture. Every connected Cayley graph on a dihedral group has a Hamilton cycle (W. Holszty´nski and R. F. E. Strube, 1978).

  2. If $p$ is a prime, then every cayley graph dihedral group $D_{p}$ is hamiltonian (W. Holszty´nski and R. F. E. Strube, 1978).

  3. All cubic cayley graphs over dihedral groups are hamiltonian (Brian Alspach and Cun-quan Zhang, 1989).

  4. If $X$ is a connected Cayley graph on the dihedral group $D_n$, $n$ even, then $X$ has a Hamilton cycle (Brian Alspach, C. C. Chen, Matthew Dean, 2010).

An interesting story about this problem happened in 2018. H. Zhou and B.Xia posted a short article in the arXiv (arXiv:1810.13311) in which they claimed to prove that every connected Cayley graph on a generalized dihedral group has a Hamilton cycle.

For a nontrivial abelian group A the generalized dihedral group $\operatorname{Dih}(A)$ of $A$ is the semidirect product of $A$ by $Z_2$ with $Z_2$ acting on $A$ by inverting elements.

But as of today, that article has been removed from the arXiv.

$\endgroup$
1
  • $\begingroup$ Thanks! This sounds about as definitive as I could hope for. It seems that my special case isn't quite resolved, but I have plenty of relevant literature I can check out before trying to iron-out the details for myself. $\endgroup$ Commented Dec 20, 2022 at 12:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .