Hamiltonian cycles and fundamental groups - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T01:02:40Z http://mathoverflow.net/feeds/question/72124 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72124/hamiltonian-cycles-and-fundamental-groups Hamiltonian cycles and fundamental groups Gjergji Zaimi 2011-08-04T23:14:36Z 2011-09-16T01:22:12Z <p>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 <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_conjecture#Cayley_graphs" rel="nofollow">Lovász conjecture</a> 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.</p> <p>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 <a href="http://ncatlab.org/nlab/show/ribbon+graph" rel="nofollow">ribbon graph</a>, and therefore it gives an embedding of $\Gamma(G)$ on a compact oriented surface $S$.</p> <p>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)$?</p> <p>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?</p> http://mathoverflow.net/questions/72124/hamiltonian-cycles-and-fundamental-groups/72127#72127 Answer by findingmistakes for Hamiltonian cycles and fundamental groups findingmistakes 2011-08-04T23:48:31Z 2011-08-04T23:48:31Z <p>What does "compact surfaces the embed in" mean? Maybe you mean "they embed in."</p>