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

The full text of this article is unavailable through your IP address: 3.138.141.202

Received 18 January 2019

Accepted 22 July 2020

Published 8 November 2021