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.