A051252

[David Wilson]

----- Original Message -----
From: "Jud McCranie" <jud.mccranie at mindspring.com>
To: "Gordon Royle" <gordon at cs.uwa.edu.au>
Cc: <seqfan at ext.jussieu.fr>
Sent: Tuesday, June 18, 2002 12:17 AM
Subject: Re: A051252


> At 08:58 AM 6/18/2002 +0800, Gordon Royle wrote:
> >Sequence A051252 is the number of ways of arranging the integers 1..2n on
a
> >circle so that the sum of any two adjacent numbers is prime.
> >
> >The numbers get large very quickly.
> >
> >But is there any proof that this can always be done?
>
> I don't know of any proof, but I expect it to be true.

I would be skeptical of a proof, given the Goldbachish character of the
problem.
I will make this observation, though.

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.

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.