Journal of Combinatorics

Volume 12 (2021)

Number 3

A $2$-regular graph has a prime labeling if and only if it has at most one odd component

Pages: 379 – 388



J. Z. Schroeder (Mosaic Center Radstock, Gostivar, Macedonia)


A graph $G$ is prime if the vertices can be distinctly labeled with the integers $1, 2, \dotsc , \lvert V (G) \rvert$ so that adjacent vertices have relatively prime labels. In this paper, we prove the long-standing conjecture that a $2$-regular graph $G$ is prime if and only if $G$ has at most one odd component.


prime labeling, regular graph, graph labeling

2010 Mathematics Subject Classification


Received 18 January 2019

Accepted 22 July 2020

Published 8 November 2021