Minimum Coprime Graph Labelings
Catherine Lee
Department of Mathematics
Yale University
New Haven, CT 06511
USA
Abstract:
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