Prime labelings of generalized Petersen graphs
Steven A. Schluchter, Justin Z. Schroeder, Kathryn Cokus, Ryan J. Ellingson, Hayley Harris, Ethan Rarity, Thomas P. Wilson · Involve a Journal of Mathematics · 2016
A graph G is called prime if the vertices of G can be assigned distinct labels 1, 2, . . ., |V (G)| such that the labels on any two adjacent vertices are relatively prime.By showing that for every even n ≤ 2.468 × 10 9 there exists s ∈ [1, n -1] such that both n + s and 2n + s are prime, we prove the generalized Peterson graph P(n, 1) is prime for all even n ∈ [4, 2.468 × 10 9].Moreover, for a fixed n we describe a method for labeling P(n, k) that is a prime labeling for multiple values of k.Using this method, we prove P(n, k) is prime for all even n ≤ 50 and all odd k ∈ [1, n/2).MSC2010: 05C78.