MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm interested in the interplay between the Hamiltonian cycles of graphs and the compact surfaces they embed in. I was doing some reading on the Lovász conjecture for Cayley graphs, I started noticing a pattern when drawing the Hamiltonian cycles once the graphs have been embedded in a compact surface, for which I don't have a counter-example, so I figured I'd ask here if such a connection has been studied.

We have a finite group $G$ together with a presentation $\langle g_1,g_2,\dots,g_n \vert R\rangle$, and a cyclic orientation on the generators. This orientation gives $\Gamma(G)$, the undirected Cayley graph of $G$, the structure of a ribbon graph, and therefore it gives an embedding of $\Gamma(G)$ on a compact oriented surface $S$.

It is conjectured that every $\Gamma (G)$ is Hamiltonian. When looking at some small examples I noticed that all homotopy classes of Hamiltonian cycles of $\Gamma (G)$, as elements of $\pi_1(S)$ have the same length. Is there an example of a group $G$ so that $\Gamma(G)$ has two Hamiltonian cycles which correspond to homotopy classes of different length in $\pi_1(S)$?

Moreover is it true that most Hamiltonian cycles will have high length in $\pi_1(S)$? This should be morally true, according to the heuristic that when a graph is Hamiltonian then it has exponentially many Hamiltonian cycles. Have such ideas been considered before, and are there non-trivial theorems of this flavor?

share|cite|improve this question
I think the heuristic should be "when a vertex-regular graph has a Hamiltonian cycle, it has exponentially many", or some similar condition that does not require a large automorphism group. Gerhard "Ask Me About System Design" Paseman, 2011.08.04 – Gerhard Paseman Aug 4 '11 at 23:21
MR2669683 may be relevant – Geoff Robinson Aug 4 '11 at 23:23
Here is more info on the paper Geoff cited. Breuer, T.; Guralnick, R. M.; Lucchini, A.; Maróti, A.; Nagy, G. P. Hamiltonian cycles in the generating graphs of finite groups. Bull. Lond. Math. Soc. 42 (2010), no. 4, 621–633: "For a finite group $G$ let $\Gamma(G)$ denote the graph defined on the non-identity elements of $G$ in such a way that two distinct vertices are connected by an edge if and only if they generate $G$. In this paper it is shown that the graph $\Gamma(G)$ contains a Hamiltonian cycle for many finite groups $G$." – Joseph O'Rourke Aug 4 '11 at 23:55
The papers by Glover and Marusic use an embedding of the Cayley graph into a surface to construct Hamilton cycles. They show that if a finite group $Q$ of order congruent to 2 modulo 4 is a quotient of $G = (a, b ; a^2, b^s, (ab)^3)$, where $s \geq 3$, then the Cayley graph of $Q$ with respect to the generating set $\{a, b, b^{-1}\}$ has a Hamilton cycle. See for instance. – Robert Bell Sep 16 '11 at 5:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.