Skip to main content
3 of 3
Fixed typo
David White
  • 30.3k
  • 9
  • 154
  • 250

Hamiltonian cycles and fundamental groups

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?

Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402