TY - JOUR
T1 - Hamiltonicity in Prime Sum Graphs
AU - Chen, Hong Bin
AU - Fu, Hung Lin
AU - Guo, Jun Yi
N1 - Publisher Copyright:
© 2020, Springer Japan KK, part of Springer Nature.
PY - 2021/1
Y1 - 2021/1
N2 - For any positive integer n, we define the prime sum graph Gn= (V, E) of order n with the vertex set V= { 1 , 2 , ⋯ , n} and E={ij:i+jisprime}. Filz in 1982 posed a conjecture that G2n is Hamiltonian for any n≥ 2 , i.e., the set of integers { 1 , 2 , ⋯ , 2 n} 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.
AB - For any positive integer n, we define the prime sum graph Gn= (V, E) of order n with the vertex set V= { 1 , 2 , ⋯ , n} and E={ij:i+jisprime}. Filz in 1982 posed a conjecture that G2n is Hamiltonian for any n≥ 2 , i.e., the set of integers { 1 , 2 , ⋯ , 2 n} 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.
KW - Filz’s conjecture
KW - Hamilton cycle
KW - Prime sum graph
UR - http://www.scopus.com/inward/record.url?scp=85092702673&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092702673&partnerID=8YFLogxK
U2 - 10.1007/s00373-020-02241-1
DO - 10.1007/s00373-020-02241-1
M3 - Article
AN - SCOPUS:85092702673
SN - 0911-0119
VL - 37
SP - 209
EP - 219
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 1
ER -