A051252 (prime circle)

[Santi Spadaro]

>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.
>

Yes, that was me.
Another interesting question related to this problem would be the following:

Call Prime Latin Square (PLS for short) of order n a latin square on the
elements {1,2,...,n} such that every two adjacent (horizontal and vertical)
entries sum to a prime number.
It is clear that n must be even. If there existed a prime circle for each n
even there would also exist a PLS of order n, namely the cyclic one
developed from the prime circle. (the latin square isomorphic to the Caley
addition table of Z_n) We are interested in counting the number of
non-isomorphic PLSs of order n. Obviously every row and column of the PLS
must be a Hamilton path in Gn.

For n=2 we have only 1 PLS, and it is cyclic:

12
21

For n=4 G_4 is the cycle with four edges so there is only one PLS and it is
cyclic:

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

For n=6 things get to be a bit more interesting, there is only one Hamilton
cycle in G_6, C=(6,5,2,3,4,1) and 2 Hamilton paths (different from any of
the circular permutations of C). P1=(6,5,2,1,4,3) and P2=(5,6,1,2,3,4)
Suppose there is a PLS not isomorphic to the cyclic one. Call it S. Then S
must have P1 or P2 has a row.

a) Suppose S has row P1=(6,5,2,1,4,3), from the definition of latin square
there must be a row beginning with 2, but the only one avaliable is
(2,3,4,1,6,5) which has the same fourth element as P1. Then S is not a
Latin square.

b) Suppose S has row (5,6,1,2,3,4). There must be some row beginning with
3, the only one avaliable is (3,4,1,6,5,2), so we have two 1s in the third
column and we reach a contradiction again.

So there is only 1 PLS of order 6, and it is cyclic.

How many non-isomorphic PLSs of order 8 are there? Does there exist a
non-cyclic one?

I don't know if this problem has ever been studied, nor if an infinite
family of PLSs has ever been constructed, but I think it would be a nice
subject for a new entry in Neil Sloane's encyclopedia.

Cheers,
Santi Spadaro


--

-- 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20020622/8ff05dc4/attachment.htm>