A051252 - Prime Circles - Summary and Update

[Santi Spadaro]

>
>Consider the graph G(m) which has vertex set {1,2,...,m} and
>where (i,j) is an edge if and only if i+j is prime. For example, the
>graph G(8) has
>
>  vertices: 1, 2, 3, 4, 5, 6, 7, 8
>  edges: (1,2) (1,4) (1,6) (2,3) (2,5) (3,4) (3,8) (4,7) (5,6) (5,8) (6,7)
>
>
>The question raised by Santi is
>
>	"Is G(2m) hamiltonian for all values of m?"
>
Another possible generalization is to change the vertex set. Call G' the
graph whose definition for the edge set is the same of G, but with vertex
set {1,4,9,16,...,n^2}.

Here is the number of Hamilton Cycles in G'(2n): 1<=n<=7

1,0,0,0,6,96,272

Note that we don't even know if G' is connected, while I have proved that G
is connected for each n:

Proof: (induction on n): for n=2 the statement is true since
V(G)={1,2} and 1+2=3 is prime. Suppose now it is true for n-1, by
Tchebishev's theorem there always is a prime p such that n<p<2n, thus
p=n+a where a <n so a is in {1,2,...,n-1}. By the induction step there
always is a path from a to any other vertex in {1,2,...,n-1}, call it
{a, x_{1},...,x_{k}}. Then {n,a,x_{1},...,x_{k}} path from n to any
other vertex. Thus G is connected. qed

Computational checking suggests that also G' is connected, but I don't know
how to prove it.

Cheers,
Santi
--