2017/07/14 by John Asplund, Asplund, John, N. Bradley Fox +1
Computer Science · Engineering · #05C78 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1707.04471
openalex publication_date 2017/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A prime labeling of a graph of order n is a labeling of the vertices with the integers 1 to~n in which adjacent vertices have relatively prime labels. A coprime labeling maintains the same criterion on adjacent vertices using any set of distinct positive integers. In this paper, we consider several families of graphs or products of graphs that have been shown to not have prime labelings and answer the natural question of how to label the vertices while minimizing the largest value in its set of labels.