Hamiltonicity in Prime Sum Graphs

Hong Bin Chen*, Hung Lin Fu, Jun Yi Guo

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)209-219
Number of pages11
JournalGraphs and Combinatorics
Issue number1
Publication statusPublished - 2021 Jan


  • Filz’s conjecture
  • Hamilton cycle
  • Prime sum graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Hamiltonicity in Prime Sum Graphs'. Together they form a unique fingerprint.

Cite this