Journal of Integer Sequences, Vol. 23 (2020), Article 20.11.4

Minimum Coprime Graph Labelings

Catherine Lee
Department of Mathematics
Yale University
New Haven, CT 06511


A coprime labeling of a graph G is a labeling of the vertices of G with distinct integers from 1 to k such that adjacent vertices have coprime labels. The minimum coprime number of G is the least k for which such a labeling exists. In this paper, we determine the minimum coprime number for a few well-studied classes of graphs, including the coronas of complete graphs with empty graphs and the joins of two paths. In particular, we resolve a conjecture of Seoud, El Sonbaty, and Mahran and two conjectures of Asplund and Fox. We also provide an asymptotic bound for the minimum coprime number of the Erdős-Rényi random graph.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A104272 A213273.)

Received July 15 2020; revised versions received October 19 2020; November 29 2020. Published in Journal of Integer Sequences, December 2 2020.

Return to Journal of Integer Sequences home page