Traversal by Prime Sum

Originator(s): ????

Question: Let Gm be the graph with vertex set {1,2,...,2m} such that xy is an edge if and only if x+y is prime. Is Gm Hamiltonian when m >= 2?

Comments/Partial results: It is easy to build a Hamiltonian cycle when 2m+1 and 2m+3 are both prime, but it is not even known if Gm is Hamiltonian for infinitely many m.

References: This question was discussed in a thread on the now-defunct mailing list COMB-L.



Index Page; Glossary


Posted 7/11/03