Open Problem Garden - Hamiltonicity of Cayley graphs - Comments

Hamiltonicity of dence Cayley graphs (re: Hamiltonicity of Cayley graphs)

Anonymous — Wed, 15 Dec 2010 11:03:29 +0100

Christofides, Hladky, and Mathe (http://arxiv.org/abs/1008.2193) proved using the Regularity Method the case when the vertex-transitive graph is sufficiently dense.

[PR] paper (re: Hamiltonicity of Cayley graphs)

Anonymous — Mon, 21 Sep 2009 23:31:03 +0200

First, link to PR paper has moved with Pak homepage. Second, it is now published in Discrete Math.

graphs vs. digraphs (re: Hamiltonicity of Cayley graphs)

md — Thu, 08 Jan 2009 02:57:26 +0100

The book you link to has examples of directed Cayley graphs with no (directed) Hamiltonian cycle. The existence of such graphs is interesting and relevant, but does not give a counterexample to the problem stated here.

Is this at all relevant? (re: Hamiltonicity of Cayley graphs)

Anonymous — Thu, 08 Jan 2009 00:09:14 +0100

Not sure but wondering if this link is at all relevant to the problem:

http://books.google.com/books?id=aSyXqtfOuU4C&pg=PA49&dq=Cayley+graph&num=100&client=firefox-a#PPA49,M1

Thanks,

- Farley

Hamiltonicity of Cayley graphs

tchow — Thu, 25 Sep 2008 03:41:46 +0200

Author(s): Rapaport-Strasser

Subject: Graph Theory » Basic G.T. » Cycles

Question Is every Cayley graph Hamiltonian?