Contents Online

# 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

#### 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