Hamiltonicity in Prime Sum Graphs

Hong Bin Chen; Hung Lin Fu; Jun Yi Guo

doi:10.1007/s00373-020-02241-1

Hamiltonicity in Prime Sum Graphs

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

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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 , ⋯ , n} and E={ij:i+jisprime}. Filz in 1982 posed a conjecture that G₂_n 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 language	English
Pages (from-to)	209-219
Number of pages	11
Journal	Graphs and Combinatorics
Volume	37
Issue number	1
DOIs	https://doi.org/10.1007/s00373-020-02241-1
Publication status	Published - 2021 Jan

Keywords

Filz’s conjecture
Hamilton cycle
Prime sum graph

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-020-02241-1

Cite this

@article{199483e2157e4e138fa75e1ed995a2c8,

title = "Hamiltonicity in Prime Sum Graphs",

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{\textquoteright}s conjecture is true for infinitely many cases.",

keywords = "Filz{\textquoteright}s conjecture, Hamilton cycle, Prime sum graph",

author = "Chen, {Hong Bin} and Fu, {Hung Lin} and Guo, {Jun Yi}",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Japan KK, part of Springer Nature.",

year = "2021",

month = jan,

doi = "10.1007/s00373-020-02241-1",

language = "English",

volume = "37",

pages = "209--219",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Hamiltonicity in Prime Sum Graphs

AU - Chen, Hong Bin

AU - Fu, Hung Lin

AU - Guo, Jun Yi

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 -

Hamiltonicity in Prime Sum Graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this