The paper proves exact minimum coprime numbers for all generalized Petersen graphs GP(n,2), for stacked triangular and pentagonal prisms, and for a degree-two Petersen variant, while conjecturing the value for odd prisms.
Minimum coprime graph labelings
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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 several 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 for the minimum coprime number of the Erd\H{o}s-R\'enyi random graph.
fields
math.CO 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Minimum Coprime Labelings of Generalized Petersen and Prism Graphs
The paper proves exact minimum coprime numbers for all generalized Petersen graphs GP(n,2), for stacked triangular and pentagonal prisms, and for a degree-two Petersen variant, while conjecturing the value for odd prisms.