Minimum Coprime Graph Labelings
Department of Mathematics
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,
(Concerned with sequences
Received July 15 2020; revised versions received October 19 2020; November 29 2020.
Published in Journal of Integer Sequences,
December 2 2020.
Journal of Integer Sequences home page