×

Hamiltonicity in prime sum graphs. (English) Zbl 1459.05149

Summary: For any positive integer \(n\), we define the prime sum graph \(G_n=(V,E)\) of order \(n\) with the vertex set \(V=\{1,2,\dots,n\}\) and \(E=\{ij: i+j\text{ is prime}\}\). Filz in 1982 posed a conjecture that \(G_{2n}\) is Hamiltonian for any \(n\geq 2\), i.e., the set of integers \(\{1,2,\dots,2n\}\) can be represented as a cyclic rearrangement so that the sum of any two adjacent integers is a prime number. With a fundamental result in graph theory and a recent breakthrough on the twin prime conjecture, we prove that Filz’s conjecture is true for infinitely many cases.

MSC:

05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertrand, J., Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu’elle renferme, Journal de l’École Royale Polytechnique, Cahier 30, 18, 123-140 (1845)
[2] Chen, JR, On the representation of a larger even integer as the sum of a prime and the product of at most two primes, Sci. Sin., 16, 157-176 (1973) · Zbl 0319.10056
[3] Chung, FRK; Graham, RL; Wilson, RM, Quasi-random graphs, Combinatorica, 9, 345-362 (1989) · Zbl 0715.05057 · doi:10.1007/BF02125347
[4] Dirac, G., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001 · doi:10.1112/plms/s3-2.1.69
[5] Erdős, P., Remarks on a paper of Pósa, Magyar Tud, Akad. Mat. Kutató Int. Kőzl., 7, 227-229 (1962) · Zbl 0114.40004
[6] Filz, A., Problem 1046, J. Recreat. Math., 14, 64 (1982)
[7] Frieze, A.M.: On the number of perfect matchings and Hamilton cycles in ”\( \epsilon \)-regular non-bipartite graphs, Electron. J. Comb. 7 (2000), publ. R57 · Zbl 0964.05053
[8] Frieze, AM; Krivelevich, M., Hamilton cycles in random subgraphs of pseudo-random graphs, Discrete Math., 256, 137-150 (2002) · Zbl 1007.05071 · doi:10.1016/S0012-365X(01)00464-2
[9] Galvin, D.: Erdős’s proof of Bertrand’s postulate, April (2006)
[10] Greenfield, L., Greenfield, S.: Some problems of combinatorial number theory related to Bertrand’s postulate, J. Integer Seq. 1 (1998), Article 98.1.2 · Zbl 1010.11007
[11] Guy, R.K.: Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, pp. 105-106, (2004) · Zbl 1058.11001
[12] Krivelevich, M.; Sudakov, B., Sparse pseudo-random graphs are Hamiltonian, J. Graph Theory, 42, 17-33 (2003) · Zbl 1028.05059 · doi:10.1002/jgt.10065
[13] Moon, J.; Moser, L., On hamiltonian bipartite graphs, Israel J. Math., 1, 163-165 (1963) · Zbl 0119.38806 · doi:10.1007/BF02759704
[14] Maynard, J., Small gaps between primes, Ann. Math., 181, 2, 383-413 (2015) · Zbl 1306.11073 · doi:10.4007/annals.2015.181.1.7
[15] Polymath, DHJ, New equidistribution estimates of Zhang type, and bounded gaps between primes, Algebra Number Theory, 8, 2067-2199 (2014) · Zbl 1307.11097 · doi:10.2140/ant.2014.8.2067
[16] Pósa, L., Hamiltonian circuits in random graphs, Discrete Math., 14, 359-364 (1976) · Zbl 0322.05127 · doi:10.1016/0012-365X(76)90068-6
[17] Tchebychev, P., Mémoire sur les nombres premiers, Journal de mathématiques pures et appliquées, Sér., 1, 366-390 (1852)
[18] Zhang, Y., Bounded gaps between primes, Ann. Math., 179, 3, 1121-1174 (2014) · Zbl 1290.11128 · doi:10.4007/annals.2014.179.3.7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.