Abstract
This paper examines the graph-theoretical concepts of consecutive prime labeling and highly total prime labeling. These are variations on prime labeling, introduced by Tout, Dabboucy, and Howalla in 1982. Consecutive prime labeling is defined here for the first time. Consecutive prime labeling requires that the labels of vertices in a graph be relatively prime to the labels of all adjacent vertices as well as all incident edges. We show that all paths, cycles, stars, and complete graphs have a consecutive prime labeling and conjecture that all simple connected graphs have a consecutive prime labeling.
This paper also expands on work introduced by Ramasubramanian and Kala on total prime graphs in 2012 and Gnanajothi and Suganya on highly total prime graphs in 2016. We extend previous results by showing that no wheel graph or hypercube graph has a highly total prime labeling. We also show that no star graph with 8 or more vertices has a highly total prime labeling. In addition, we introduce millipede graphs, a new subfamily of caterpillar graphs, and show that certain millipede graphs do not have a highly total prime labeling.
Faculty Sponsor
Janet Fierson
Recommended Citation
Scholle, Robert
(2019)
"Consecutive Prime and Highly Total Prime Labeling in Graphs,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 20:
Iss.
2, Article 2.
Available at:
https://scholar.rose-hulman.edu/rhumj/vol20/iss2/2