Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.8

Coprime and Prime Labelings of Graphs


Adam H. Berliner
Department of Mathematics, Statistics, and Computer Science
St. Olaf College
Northfield, MN 55057
USA

Nathaniel Dean
Department of Mathematics
Texas State University
San Marcos, TX 78666
USA

Jonelle Hook
Department of Mathematics and Computer Science
Mount St. Mary's University
Emmitsburg, MD 21727
USA

Alison Marr
Department of Mathematics and Computer Science
Southwestern University
Georgetown, TX 78626
USA

Aba Mbirika
Department of Mathematics
University of Wisconsin-Eau Claire
Eau Claire, WI 54702
USA

Cayla D. McBee
Department of Mathematics and Computer Science
Providence College
Providence, RI 02918
USA

Abstract:

A coprime labeling of a simple graph of order n is a labeling in which adjacent vertices are given relatively prime labels, and a graph is prime if the labels used can be taken to be the first n positive integers. In this paper, we consider when ladder graphs are prime and when the corresponding labeling may be done in a cyclic manner around the vertices of the ladder. Furthermore, we discuss coprime labelings for complete bipartite graphs.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A104272 A213273 A213806.)

Received March 12 2016; revised versions received June 7 2016. Published in Journal of Integer Sequences, June 13 2016.

Return to Journal of Integer Sequences home page