Abstract
A graph $G$ is called prime if the vertices of $G$ can be assigned distinct labels $1,2,...,|V(G)|$ such that the labels on any two adjacent vertices are relatively prime. By showing that for every even $n\leq 2.468\times 10^9$ there exists $s\in [1,n-1]$ such that both $n+s$ and $2n+s$ are prime, we prove the generalized Peterson graph $P(n,1)$ is prime for all even $n\in [4,2.468\times 10^9]$. Moreover, for a fixed $n$ we describe a method for labeling $P(n,k)$ that is a prime labeling for multiple values of $k$. Using this method, we prove $P(n,k)$ is prime for all even $n\leq 50$ and all odd $k\in [1,n/2)$.
Type
Publication
In Involve
