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, \ldots, |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.