Minimum Coprime Labelings of Generalized Petersen and Prism Graphs
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,
Received July 22 2020; revised version received February 10 2021; February 14 2021.
Published in Journal of Integer Sequences,
February 15 2021.
Journal of Integer Sequences home page