Hamiltonicity in Prime Sum Graphs
- PDF / 468,325 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 201 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Hamiltonicity in Prime Sum Graphs Hong-Bin Chen1
•
Hung-Lin Fu2 • Jun-Yi Guo3
Received: 22 November 2019 / Revised: 29 September 2020 / Accepted: 9 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract For any positive integer n, we define the prime sum graph Gn ¼ ðV; EÞ of order n with the vertex set V ¼ f1; 2; ; ng and E ¼ fij : i þ j is prime g. Filz in 1982 posed a conjecture that G2n is Hamiltonian for any n 2, i.e., the set of integers f1; 2; ; 2ng 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. Keywords Hamilton cycle Prime sum graph Filz’s conjecture
Mathematics Subject Classification 05C45
1 Introduction This paper is motivated from a result concerning prime numbers. Theorem 1 [10] The set of integers f1; 2; 3; ; 2ng, n 1, can be partitioned into pairs fai ; bi g such that ai þ bi is prime for all i ¼ 1; 2; ; n.
H.-B. Chen: The author is supported by MOST 105-2115-M-035-006-MY2 and MOST 107-2115-M035-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. H.-L. Fu Supported by MOST 106-2115-M-009-008. J.-Y. Guo Supported by MOST 106-2115-M-003-007. & Hong-Bin Chen [email protected] 1
Department of Applied Mathematics, National Chung Hsing University, Taichung 40249, Taiwan
2
Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan
3
Department of Mathematics, National Taiwan Normal University, Taipei 11677, Taiwan
123
Graphs and Combinatorics
Taking n ¼ 10 for an example, f1; 2; ; 20g can be partitioned into pairs so that the sum of each pair is a prime number, as shown in Fig. 1. Theorem 1 was proved by Greenfield and Greenfield [10] and reproduced by Galvin [9]. This lovely result follows with an elegant proof from the well-known Bertrand’s Postulate, or sometimes called Bertrand–Chebyshev Theorem [1, 17]. Theorem 2 [1, 17] For any positive integer n [ 1, there is at least a prime p such that n\p\2n. As the proof of Theorem 1 is short, we demonstrate it in the following to make this paper self-contained. The proof is by induction on n. For n ¼ 1, it is trivial. Assume that the statement is true for any k\n. By Bertrand–Chebyshev Theorem, there exists a prime p 2 ð2n; 4nÞ. We may assume that the prime p ¼ 2n þ k for some 1 k\2n. Then the set of integers fk; k þ 1; ; 2n 1; 2ng can be partitioned into pairs fk; 2ng; fk þ 1; 2n 1g; ; fn þ bk=2c; n þ dk=2eg (the last is valid since k is odd). Each of the pairs sums to the prime 2n þ k. By the induction hypothesis, the set of remaining integers f1; 2; ; k 1g has the property, too. Thus, the whole set f1; 2; :2ng can be partitioned into pairs so tha
Data Loading...
