Hamiltonicity in Prime Sum Graphs

Hong Bin Chen, Hung Lin Fu, Jun Yi Guo

Research output: Contribution to journalArticlepeer-review

Abstract

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
JournalGraphs and Combinatorics
DOIs
Publication statusAccepted/In press - 2020

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

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

Cite this