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

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n3.a1

Author

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

Abstract

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

Received 18 January 2019

Accepted 22 July 2020

Published 8 November 2021