A051252 - Prime Circles - Summary and Update
Santi Spadaro
santi_spadaro at virgilio.it
Tue Jun 25 22:48:46 CEST 2002
>
>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
--
More information about the SeqFan
mailing list