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

0, 0, 0, 0, 1, 2, 4, 16, 60, 186, 433, 2215, 11788, 76539, 414240, 2202215, 9655287, 69748712, 444195809, 3703859949, 26688275292, 201673532931, 1265944917365, 11801735916539, 92511897525830, 753795624276096, 5237677221537738, 41074291450736424, 280906738160126067

Offset: 1

Author

Zhi-Wei Sun, Aug 28 2013

Keywords

• nonn
• hard

Comments

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.

Note that this conjecture is different from the prime circle problem in A051252 though they look similar.

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);

if n = 2*k + 1 then G_n contains a Hamiltonian cycle

(1,3,5,2,7,9,...,2k-5,2k,2k-3,2k-1,2k+1,2k-2,2k-4,...,6,4).

We have got Chen's approval to include his proof here.

Examples

			a(5) = 1 since G_5 contains the unique Hamiltonian cycle (1,4,2,5,3).
a(6) = 2 since G_6 contains exactly two Hamiltonian cycles: (1,3,5,2,4,6) and (1,4,2,5,3,6).
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).
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).
a(9) > 0 since (1,3,5,7,9,2,4,6,8) is a Hamiltonian cycle in G_9.
a(10) > 0 since (1,3,5,2,4,6,9,7,10,8) is a Hamiltonian cycle in G_{10}.
a(11) > 0 since (1,3,5,10,8,11,9,2,7,4,6) is a Hamiltonian cycle in G_{11}.
a(12) > 0 since (1,3,8,10,5,2,7,4,6,11,9,12) is a Hamiltonian cycle in G_{12}.
		

Links

• Hong-Bin Chen, Hung-Lin Fu, Jun-Yi Guo, Beyond Hamiltonicity of Prime Difference Graphs, arXiv:2003.00729 [math.CO], 2020.
• S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014. See Table II.
• Index entries for sequences related to graphs, Hamiltonian

Crossrefs

Cf. A000040, A051239, A051252, A185645, A227050, A242527, A242528.

Programs

Mathematica

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 *)

Extensions

a(9)-a(17) from Alois P. Heinz, Aug 28 2013

a(18)-a(19) from Stanislav Sykora, May 30 2014

a(20)-a(29) from Max Alekseyev, Jul 04 2014