2019/08/16 by Asplund, John, Fox, N. Bradley
#05C78 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1908.06051
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.