12
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Aug 4, 2011 at 23:21
  • $\begingroup$ MR2669683 may be relevant $\endgroup$
    – Geoff Robinson
    Aug 4, 2011 at 23:23
  • 1
    $\begingroup$ 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$." $\endgroup$
    – Joseph O'Rourke
    Aug 4, 2011 at 23:55
  • $\begingroup$ 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. $\endgroup$
    – Robert Bell
    Sep 16, 2011 at 5:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.