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

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.

Keywords

prime labeling, regular graph, graph labeling

2010 Mathematics Subject Classification

05C78

Full Text (PDF format)

Received 18 January 2019

Accepted 22 July 2020

Published 8 November 2021