Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 generatorss. 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|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 arxiv.org/PS_cache/math/pdf/0508/0508647v1.pdf for instance. –  Robert Bell Sep 16 '11 at 5:05
add comment

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.