TY - JOUR

T1 - Hamiltonicity in Prime Sum Graphs

AU - Chen, Hong Bin

AU - Fu, Hung Lin

AU - Guo, Jun Yi

N1 - Funding Information:
H.-L. Fu Supported by MOST 106-2115-M-009-008.
Funding Information:
J.-Y. Guo Supported by MOST 106-2115-M-003-007.
Funding Information:
H.-B. Chen: The author is supported by MOST 105-2115-M-035-006-MY2 and MOST 107-2115-M-035-003-MY2, and the research is partly done while the author was a member of Department of Applied Mathematics, Feng Chia University, Taichung 40724, Taiwan.
Publisher Copyright:
© 2020, Springer Japan KK, part of Springer Nature.

PY - 2020

Y1 - 2020

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

VL - 37

SP - 209

EP - 219

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 1

ER -