A051252
Jim Nastos
nastos at cs.ualberta.ca
Wed Jun 19 08:00:51 CEST 2002
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
More information about the SeqFan
mailing list