|
%I #51 Jun 03 2020 22:13:47
%S 0,0,0,0,1,2,4,16,60,186,433,2215,11788,76539,414240,2202215,9655287,
%T 69748712,444195809,3703859949,26688275292,201673532931,1265944917365,
%U 11801735916539,92511897525830,753795624276096,5237677221537738,41074291450736424,280906738160126067
%N Number of Hamiltonian cycles in the undirected simple graph G_n with vertices 1,...,n which has an edge connecting vertices i and j if and only if |i-j| is prime.
%C Conjecture: a(n) > 0 for all n > 4. In other words, for each n = 5,6,... there is a permutation i_1,...,i_n of 1,...,n such that |i_1-i_2|, |i_2-i_3|, ..., |i_{n-1}-i_n| and |i_n-i_1| are all prime.
%C Note that this conjecture is different from the prime circle problem in A051252 though they look similar.
%C On August 30 2013, Yong-Gao Chen (from Nanjing Normal University) confirmed the conjecture for n > 12 as follows: If n = 2*k then G_n contains a Hamiltonian cycle (1,3,5,2,7,9,...,2k-5,2k-3,2k,2k-2,2k-4,2k-1,2k-6,2k-8,...,6,4);
%C if n = 2*k + 1 then G_n contains a Hamiltonian cycle
%C (1,3,5,2,7,9,...,2k-5,2k,2k-3,2k-1,2k+1,2k-2,2k-4,...,6,4).
%C We have got Chen's approval to include his proof here.
%H Hong-Bin Chen, Hung-Lin Fu, Jun-Yi Guo, <a href="https://arxiv.org/abs/2003.00729">Beyond Hamiltonicity of Prime Difference Graphs</a>, arXiv:2003.00729 [math.CO], 2020.
%H S. Sykora, <a href="http://dx.doi.org/10.3247/SL5Math14.002">On Neighbor-Property Cycles</a>, <a href="http://ebyte.it/library/Library.html#math">Stan's Library</a>, Volume V, 2014. See Table II.
%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>
%e a(5) = 1 since G_5 contains the unique Hamiltonian cycle (1,4,2,5,3).
%e a(6) = 2 since G_6 contains exactly two Hamiltonian cycles: (1,3,5,2,4,6) and (1,4,2,5,3,6).
%e a(7) = 4 since G_7 contains exactly four Hamiltonian cycles: (1,3,5,2,7,4,6), (1,3,5,7,2,4,6), (1,4,2,7,5,3,6) and (1,4,7,2,5,3,6).
%e a(8) = 16 since G_8 contains exactly 16 Hamiltonian cycles: (1,3,5,2,7,4,6,8), (1,3,5,7,2,4,6,8), (1,3,6,4,2,7,5,8), (1,3,6,4,7,2,5,8), (1,3,6,8,5,2,7,4), (1,3,6,8,5,7,2,4), (1,3,8,5,2,7,4,6), (1,3,8,5,7,2,4,6), (1,4,2,7,5,3,6,8), (1,4,2,7,5,3,8,6), (1,4,2,7,5,8,3,6), (1,4,7,2,5,3,6,8), (1,4,7,2,5,3,8,6), (1,4,7,2,5,8,3,6), (1,6,4,2,7,5,3,8), (1,6,4,7,2,5,3,8).
%e a(9) > 0 since (1,3,5,7,9,2,4,6,8) is a Hamiltonian cycle in G_9.
%e a(10) > 0 since (1,3,5,2,4,6,9,7,10,8) is a Hamiltonian cycle in G_{10}.
%e a(11) > 0 since (1,3,5,10,8,11,9,2,7,4,6) is a Hamiltonian cycle in G_{11}.
%e a(12) > 0 since (1,3,8,10,5,2,7,4,6,11,9,12) is a Hamiltonian cycle in G_{12}.
%t Table[Length[FindHamiltonianCycle[Graph[Flatten[Table[If[PrimeQ[Abs[i - j]], i \[UndirectedEdge] j, {}], {i, 1, n}, {j, i + 1, n}]]], Infinity]], {n, 1, 15}] (* _Robert Price_, Apr 04 2019 *)
%o (C++) listed in the link (S. Sykora)
%Y Cf. A000040, A051239, A051252, A185645, A227050, A242527, A242528.
%K nonn,hard
%O 1,6
%A _Zhi-Wei Sun_, Aug 28 2013
%E a(9)-a(17) from _Alois P. Heinz_, Aug 28 2013
%E a(18)-a(19) from _Stanislav Sykora_, May 30 2014
%E a(20)-a(29) from _Max Alekseyev_, Jul 04 2014
|
