On a Prime Labeling Conjecture

Abstract

A graph with vertex set $V$ is said to have a prime labeling if its vertices are labelled with distinct integers from $\{1,2,\dots ,|V|\}$ such that for each edge $xy$, the labels assigned to $x$ and $y$ are relatively prime. A graph that admits a prime labeling is called a prime graph. It has been conjectured $[1]$ that when $n$ is a prime integer and $m<n$, the planar grid $P_m\times P_n$ is prime. We prove the conjecture and also that $P_n\times P_n$ is prime when $n$ is a prime integer.