Journal of Integer Sequences, Vol. 24 (2021), Article 21.3.5

Minimum Coprime Labelings of Generalized Petersen and Prism Graphs

John Asplund
Metron, Inc.
Reston, VA 20190

N. Bradley Fox
Department of Mathematics and Statistics
Austin Peay State University
Clarksville, TN 37044


A coprime labeling of a graph of order n is an assignment of distinct positive integer labels in which adjacent vertices have relatively prime labels. Restricting labels to only the set 1 to n results in a prime labeling. In this paper, we consider families of graphs in which a prime labeling cannot exist with the goal being to minimize the largest value of the labeling set, resulting in a minimum coprime labeling. In particular, prism graphs, generalized Petersen graphs with k = 2, and stacked prism graphs are investigated for minimum coprime labelings.

Full version:  pdf,    dvi,    ps,    latex    

Received July 22 2020; revised version received February 10 2021; February 14 2021. Published in Journal of Integer Sequences, February 15 2021.

Return to Journal of Integer Sequences home page