Hamiltonian cycles and fundamental groups

2011-08-04T23:14:36Z

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?

Answer by findingmistakes for Hamiltonian cycles and fundamental groups

2011-08-04T23:48:31Z

What does "compact surfaces the embed in" mean? Maybe you mean "they embed in."

Hamiltonian cycles and fundamental groups - MathOverflow

Hamiltonian cycles and fundamental groups

Answer by findingmistakes for Hamiltonian cycles and fundamental groups