A051252

[Jim Nastos]

On Tue, 18 Jun 2002, David Wilson wrote:

> Let Gn be the graph whose vertices are the integers 1 through 2n, and whose
> edges
> connect pairs of integers whose sum is prime.  The problem then devolves to
> counting the Hamiltonian circuits in Gn.

  Yes interesting - an individual in a couple of newsgroups (a couple of 
days ago in sci.math.research and maybe a week ago in 
(?)alt.combinatorics) introduced this graphs as "a curious graph," showed 
its connectedness (equivalence to Tsebycheff's theorem) and conjectured 
its Hamiltonianicity. For the Halmiltonian problem, he noted that the 
graph is bipartite but did not know where to go from there.

> For a general graph, finding a single Hamiltonian circuit is NP-complete.
> From this I would suspect that, for a general graph, confirming 
> existence or counting Hamiltonian circuits is just as hard.  I also 
> suspect that Gn does not have enough useful structure to reduce the 
> difficulty of counting the Hamiltonian circuits.

  I would agree that the graph is sufficiently complex that counting Ham 
cycles would be difficult (i.e. no simple polynomial-time algorithm) but I 
would think that the primes would have enough structure to prove that 
there always exists some.
  Probabilistically, verifying the graph on 2n nodes for very large 2n is 
Hamiltonian then noticing that new vertices added will have many (about 
log(2n)) (arbitrarily many) edges, it would seem like it's a provable 
property.

-- 
Jim Nastos, B.Math, B.Ed                Office: 117 Athabasca Hall
MSc Candidate                           Office Phone: (780) 492-5046
University Of Alberta                   Edmonton, Alberta
Department Of Computing Science         T6G 2H1
nastos at cs.ualberta.ca
http://www.cs.ualberta.ca/people/grad/nastos.html