\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\usepackage{pgf,tikz}
\newenvironment{packedItem}{
\begin{itemize}
\setlength{\itemsep}{1pt}
\setlength{\parskip}{0pt}
\setlength{\parsep}{0pt}
}{\end{itemize}}
\DeclareMathOperator{\GP}{GP}
\newcommand{\SSSS}{\mathfrak S}
\newcommand{\pr}{\mathfrak{pr}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{obs}[theorem]{Observation}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Minimum Coprime Labelings of Generalized \\
\vskip .1in
Petersen and Prism Graphs
}
\vskip 1cm
\large
John Asplund\\
Metron, Inc. \\
Reston, VA 20190 \\
USA\\
\href{mailto:asplund@metsci.com}{\tt asplund@metsci.com}\\
\ \\
N. Bradley Fox\\
Department of Mathematics and Statistics \\
Austin Peay State University \\
Clarksville, TN 37044 \\
USA\\
\href{mailto:foxb@apsu.edu}{\tt foxb@apsu.edu} \\
\end{center}
\vskip .2 in
\begin{abstract}
A coprime labeling of a graph of order $n$ is an assignment of distinct
positive integer labels in which adjacent vertices have relatively prime
labels. Restricting labels to only the set $1$ to $n$ results in a prime
labeling. In this paper, we consider families of graphs in which a prime
labeling cannot exist with the goal being to minimize the largest value of
the labeling set, resulting in a minimum coprime labeling. In particular,
prism graphs, generalized Petersen graphs with $k=2$, and stacked prism
graphs are investigated for minimum coprime labelings.
\end{abstract}
\section{Introduction}\label{intro}
Let $G$ be a simple graph of order $n$ with vertex set $V$. We denote an edge between two adjacent vertices $v$ and $w$ as $vw$. A \textit{coprime labeling} of $G$ is a labeling of $V$ using distinct labels from the set $\{1,\ldots,m\}$ for some integer $m\geq n$ in which adjacent vertices are labeled by relatively prime integers. If the integers $1,\ldots, n$ are used as the labeling set, the labeling is called a \textit{prime labeling}, and $G$ is a \textit{prime graph} or is simply referred to as \textit{prime}. For graphs in which no prime labeling exists, our goal is to minimize the value $m$, the largest label in the coprime labeling. This smallest possible value $m$ for a coprime labeling of $G$, denoted by $\pr(G)$, is the \textit{minimum coprime number} of $G$, and a coprime labeling with $\pr(G)$ as the largest label is a \textit{minimum coprime labeling} of~$G$. A prime graph would have a minimum coprime number of $\pr(G)=n$.
Prime labelings of graphs were developed by Roger Entringer and first introduced by Tout, Dabboucy, and Howalla~\cite{TDH}. Numerous classes of graphs over the past forty years have been shown to be prime, as well as many classes for which a prime labeling has been shown to not exist. A summary of these results can be seen in Gallian's dynamic survey of graph labelings~\cite{Gallian}. Most of our upcoming results center around the concept of minimum coprime labelings, which were first studied by Berliner et al.~\cite{Berliner} with their investigation of complete bipartite graphs of the form $K_{n,n}$.
Asplund and Fox~\cite{AF} continued this line of research by determining the minimum coprime number for classes of graphs such as complete graphs, wheels, the union of two odd cycles, the union of a complete graph with a path or a star, powers of paths and cycles, and the join of paths and cycles. Recently, Lee~\cite{Lee} made further progress on the minimum coprime number of the join of paths and complete bipartite graphs, in addition to investigating minimum coprime numbers of random subgraphs.
The focus of this paper is to determine the minimum coprime number of prism graphs, which are equivalent to the Cartesian product of a cycle of length $n$ and a path with $2$ vertices, denoted as $C_n\square P_2$. Additionally, a prism graph is equivalent to the generalized Petersen graphs when $k=1$. In the next section, we include preliminary material regarding the classes of graphs we will investigate and previous research on prime labelings of these graphs. In Section~\ref{prisms}, we construct minimum coprime labelings of prism graphs $\GP(n,1)$ for several specific cases of odd~$n$ as well as present a conjecture for all sizes of odd prisms. Section~\ref{GP2} includes results on the minimum coprime number of the generalized Petersen graph $\GP(n,2)$, a graph which is not prime for any value $n$. Section~\ref{stacked} consists of results on minimum coprime number of stacked prism graphs, and finally we investigate a variation of a generalized Petersen graph in Section~\ref{GPvariation}.
\section{Preliminary material}\label{prelim}
An important feature of a graph $G$ that aides in determining whether a prime labeling may exist or if a minimum coprime labeling should instead be investigated is its \textit{independence number}, denoted by~$\alpha(G)$. Since even number labels must be assigned to independent vertices, the following criteria, first introduced by Fu and Huang~\cite{FH}, eliminates the possibility of a prime labeling on many classes of graphs.
\begin{lemma}{\normalfont \cite{FH}}\label{ind}
If $G$ is prime, then the independence number of $G$ must satisfy $\alpha(G)\geq \left\lfloor \frac{|V(G)|}{2}\right\rfloor$.
\end{lemma}
The generalized Petersen graph, denoted $\GP(n,k)$ where $n\geq 3$ and $1\leq k \leq \lfloor (n-1)/2\rfloor$, consists of $2n$ vertices $v_1,\ldots, v_n,u_1,\ldots, u_n$. It has $3n$ edges described by $v_i v_{i+1}$, $u_i u_{i+k}$, and $v_i u_i$ where indices are calculated modulo $n$. In the particular case of $k=1$, the two sets of vertices form $n$-gons that are connected to form a prism graph, which will be our first graph that we investigate.
When $n$ is odd, $\GP(n,1)$ consists of two odd cycles connected by a perfect matching. Only $(n-1)/2$ vertices on each cycle can be independent, hence $\alpha(\GP(n,1))=n-1$ for odd $n$. Then by Lemma~\ref{ind}, $\GP(n,1)$ is not prime in this case, a property which extends to any value of $k$ when $n$ is odd. In fact, $\GP(n,k)$ was proven to not be prime by Prajapati and Gajjar~\cite{PG} for any odd value of $n$ as well as when $n$ and $k$ are both even. Independence numbers for generalized Petersen graphs for certain cases have been determined~\cite{BHM,BEA,FGS} that help provide bounds for the minimum coprime numbers of $\GP(n,k)$ in the non-prime cases.
The remaining case of $\GP(n,k)$ with $n$ even and $k$ odd is conjectured to be prime for all such $n$ and $k$. When $k=1$, the prism graph $\GP(n,1)$ has been proven to be prime in many specific cases by Haque et al.~\cite{HLYZ} such as when $2n+a$ or $n+a$ are prime for several small values of $a$. Additional cases of $\GP(n,1)$ were proven to be prime~\cite{PG}. Dean~\cite{dean} proved the conjecture that all ladders are prime. Since ladders are simply prism graphs with two edges removed, one might expect his prime labeling to carry over to $\GP(n,1)$. However, when applying this labeling to $\GP(n,1)$, these two additional edges do not maintain the relatively prime condition for all~$n$.
While some results have been found on $\GP(n,3)$, see~\cite{HLYZ2}, most work involving prime labelings of the generalized Petersen graph has been focused on the prism graph. Schluchter et al.~\cite{SSCEHRW} made a number theoretic conjecture to bolster the conjecture that $\GP(n,1)$ is prime for all even $n$. Conjecture 2.1~\cite{SSCEHRW} stated that for any even integer $n$, there exists an $s\in [1,n-1]$ such that $n+s$ and $2n+s$ are prime. By verifying this conjecture for all even $n$ up to $2.468\times 10^9$, they demonstrated $\GP(n,1)$ is prime with even $n$ up to that value.
We conclude this section with the following observations, which will be used without citation in many of the theorems throughout this paper.
\begin{obs}\label{easy}
For positive integers $a,b$, and $k$, the following hold:
\begin{packedItem}
\item $\gcd(a,b)=\gcd(ka,b)$.
\item $\gcd(a,b)=\gcd(a-b,b)$.
\item $\gcd(a,b)=\gcd(a+b,b)$.
\item If $a+b$ is prime, then $\gcd(a,b)=1$.
\item If $a-b$ is a prime $p$ and both $a$ and $b$ are not multiples of $p$, then $\gcd(a,b)=1$.
\end{packedItem}
\end{obs}
\section{Prism graphs}\label{prisms}
In this section, we provide several specific results for the minimum coprime number of $\GP(n,1)$ and conjecture that $\pr(\GP(n,1))=2n+1$ for all odd $n$. Many of the theorems follow a similar proof strategy, but a general construction extended from our techniques seems unlikely without the resolution of longstanding number theory conjectures. See Figure~\ref{gp11_1} for an example of our first result showing a minimum coprime labeling for the prism $\GP(11,1)$.
\begin{figure}[H]
\centering
\includegraphics[width=2.5in]{prism11.eps}
\caption{Minimum coprime labeling for $\GP(11,1)$}
\label{gp11_1}
\end{figure}
\begin{theorem}\label{n}
If $n$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We construct a labeling $\ell$ in the following manner. We label $v_1,\ldots, v_n$ as $1,\ldots, n$ and $u_1,\ldots, u_n$ with $n+1,\ldots, 2n-1, 2n+1$ respectively. All adjacent pairs in $\{v_1,\ldots,v_n\}$ and in $\{u_1,\ldots,u_n\}$ have consecutive labels except for $v_1v_n$, $u_{n-1}u_n$, and $u_1u_n$. The first pair includes~$1$ as one of the labels, and the second pair is labeled by consecutive odd labels. Lastly, $\ell(u_1)$ and $\ell(u_n)$ are relatively prime since $\gcd(n+1,2n+1)=\gcd(2n+2,2n+1)=1$.
It remains to show that the labels $\ell(u_i)$ and $\ell(v_i)$ are relatively prime for each $i$. For $i\leq n-1$, the difference between the labels on $v_i$ and $u_i$ is $n$. Since $n$ is assumed to be prime, these pairs are relatively prime by Observation~\ref{easy}. Finally when $i=n$, we have $\gcd(2n+1,n)=\gcd(n+1,n)=1$. Therefore, this is a coprime labeling, hence $\pr(\GP(n,1))\leq 2n+1$. Since the independence number of $\GP(n,1)$ is $n-1$ when $n$ is odd, a prime labeling is not possible, making $\pr(\GP(n,1))>2n$. Thus when $n$ is prime, we have $\pr(\GP(n,1))=2n+1$.
\end{proof}
\begin{theorem}\label{n+2}
If $n+2$ is prime, then $\pr(GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We construct a labeling $\ell$ in the following manner. First we label $v_1,\ldots,v_n$ with the numbers $1,\ldots,n$, respectively, and then the vertices $u_1,\ldots,u_n$ with the labels $n+3,\ldots, 2n+1, n+2$, respectively.
Edges between vertices in $\{v_1,\ldots,v_n\}$ have vertices with consecutive labels or contain the label~$1$, and so
$\gcd(\ell(v_i),\ell(v_{i+1}))=\gcd(\ell(v_1),\ell(v_n))=1$. Edges between vertices in $\{u_1,\ldots,u_n\}$ have vertices with consecutive labels or with labels $n+2$ and $2n+1$ in which $n+2$ is prime. Hence the labels between pairs of adjacent vertices in $\{u_1,\ldots,u_n\}$ are relatively prime. For $i=1,\ldots, n-1$, since the difference of the labels on vertices $u_i$ and $v_i$ is $n+2$, which is prime, $\gcd(\ell(u_i),\ell(v_i))=1$. Lastly, $u_n$ and $v_n$ are labeled by consecutive odd integers. Therefore, we have a coprime labeling that is minimal since $\GP(n,1)$ is not prime for odd $n$. Thus, $\pr(\GP(n,1))=2n+1$ assuming $n+2$ is prime.
\end{proof}
\begin{theorem}\label{2n+1}
If $2n+1$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We construct a labeling $\ell$ in the following manner. First we label $v_1,\ldots, v_n$ as $1,\ldots, n$ as in last theorem, but we label $u_1,\ldots, u_n$ in reverse order as $2n+1, 2n-1, 2n-2,\ldots,n+1$.
Edges connecting vertices in $\{v_1,\ldots,v_n\}$ have consecutive labels or contain the label $1$, and so $\gcd(\ell(v_i),\ell(v_{i+1}))=\gcd(\ell(v_1),\ell(v_n))=1$.
Edges between vertices in $\{u_1,\ldots,u_n\}$ have vertices with consecutive labels, with consecutive odd integer labels, or with the pair of labels $n+1$ and $2n+1$, and so the labels on these adjacent vertices are relatively prime.
For each $i=2,\ldots, n$, since $\ell(u_i)+\ell(v_i)=2n+1$, we know that $\gcd(\ell(u_i),\ell(v_i))=1$ by Observation~\ref{easy} because $2n+1$ is prime. Finally, the edge $u_1v_1$ includes the label $1$ on $u_1$. Thus, this is a coprime labeling that shows $\pr(\GP(n,1))=2n+1$ when $2n+1$ is prime.
\end{proof}
\begin{theorem}\label{2n-1}
If $2n-1$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
Notice that when $n\equiv 2\pmod{3}$, then $2n-1$ is divisible by 3, so we may assume $n\not\equiv 2\pmod{3}$.
If $n\equiv 0\pmod{3}$, we construct a labeling $\ell$ by first labeling $v_1,\ldots,v_n$ as $1, 2,\ldots, n-1, 2n-1$ and then label $u_1,\ldots,u_n$ as $2n-2, 2n-1,\ldots, n, 2n+1$. One can see the pairs $u_iu_{i+1}$ and $v_iv_{i+1}$ have relatively prime labels, where $\gcd(\ell(u_1),\ell(u_n))=\gcd(2n+1,2n-2)=1$ since $n$ is a multiple of $3$ in this case. The pairs $u_iv_i$ have relatively prime labels for $i=1,\ldots, n-1$ since $\ell(u_i)+\ell(v_i)=2n+1$, which is assumed to be prime. Whereas for $i=n$, $\gcd(\ell(u_n),\ell(v_n))=1$ since these are consecutive odd integers.
If $n\equiv 1\pmod{3}$, then use the same labeling as the previous case except $\ell(u_1)=2n-2$ instead of $2n$. This is a coprime labeling for similar reasoning as our first case, except now the pair of labels $2n$ and $2n+1$ on $u_1$ and $u_n$ are consecutive, and the labels $2n$ and $2n-3$ on $u_1$ and $u_2$ are relatively prime since $n\equiv 1\pmod{3}$. In each case, the labeling is a minimum coprime labeling, proving $\pr(\GP(n,1))=2n+1$ assuming $2n-1$ is prime.
\end{proof}
For further results regarding minimum coprime labelings of prism graphs in other specific cases, see Appendix A. Using Theorems~\ref{n}--\ref{2n-1}, along with Theorems~\ref{n+4}--\ref{n+6} in the Appendix, an explicit minimum coprime labeling is given for $\GP(n,1)$ for all odd $n$ up to 1641. The following is a more general construction assuming a particular pair of prime numbers exists.
\begin{theorem}\label{conj}
Let $n\geq 3$ be odd. If there exists an $s\in [3,n-1]$ such that $n+s+1$ and $2n+s+2$ are prime, then $\pr(\GP(n,1))= 2n+1$.
\end{theorem}
\begin{proof}
We use the labeling defined in Table~\ref{s-conj} where the top row represents the vertices $v_1,\ldots,v_n$ and the bottom row represents the vertices $u_1,\ldots,u_n$. The vertex pairs on edges of the form $u_1v_1$, $u_iu_{i+1}$ and $v_iv_{i+1}$ either contain the label 1, are consecutive integers, are consecutive odd integers, or are the relatively prime pair $n+1$ and $2n+1$. The adjacent pairs $u_iv_i$ for $i=2,\ldots, s$ have labels that add to $n+s+1$, and the pairs $u_iv_i$ for $i=s+1, \ldots, n$ are labeled by integers whose sum is $2n+s+2$. Since both of these sums are assumed to be prime, the labels on those pairs are relatively prime as well. Thus, since $\GP(n,1)$ is not prime when $n$ is odd, we have constructed a minimum coprime labeling proving that $\pr(\GP(n,1))=2n+1$ if such a value $s$ exists.
\end{proof}
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & $\cdots$ & $s-1$ & $s$ & $s+1$ & $s+2$ & $\cdots$ & $n-1$ & $n$ \\
\hline
$n+s+1$ & $n+s-1$ & $\cdots$ & $n+2$ & $n+1$ & $2n+1$ & $2n$ & $\cdots$ & $n+s+3$ & $n+s+2$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{conj}}
\label{s-conj}
\end{table}
Recall that Conjecture 2.1~\cite{SSCEHRW} states that for all even integers $n$, there is an $s1$ we then define the following labeling for the block of ten vertices $v_{5k+1},\ldots,v_{5k+5},u_{5k+1},\ldots,u_{5k+5}$ for each $1\leq k 70$, we assign for $i>70$ and $j=1,\ldots 5$ the label $\ell(v_{i,j})=\ell(v_{i-70,j})+420$. Since the greatest difference between adjacent labels on the first~$70$ pentagons was $10$, only common prime factors $2$, $3$, $5$, and $7$ need to be considered. The shift by $420$, which only has these four prime numbers as factors, results in the relatively prime condition remaining satisfied for all vertex pairs with $i\geq 71$. The only exceptions that need to be verified are edges of the form $v_{70m,j}v_{70m+1,j}$ for some positive integer~$m$. We have the following pairs of labels that are adjacent:
\begin{align*}
\{\ell(v_{70m,1})=420m-5&,\; \ell(v_{70m+1,1})=420m+3\},\\
\{\ell(v_{70m,2})=420m-1&,\; \ell(v_{70m+1,2})=420m+2\},\\
\{\ell(v_{70m,3})=420m-2&,\; \ell(v_{70m+1,3})=420m+1\},\\
\{\ell(v_{70m,4})=420m-3&,\; \ell(v_{70m+1,4})=420m+4\},\\
\{\ell(v_{70m,5})=420m-4&,\; \ell(v_{70m+1,5})=420m+5\}.
\end{align*}
The first pair is relatively prime since they are odd integers differing by a power of $2$. The second, third, and fifth pairs are not multiples of 3 and are separated by either 3 or 9. Finally, the fourth pair are separated by 7, but since 7 divides 420, neither of these are multiples of 7. Thus, these adjacent pairs of vertices all have relatively prime labels, making this a coprime labeling for $n\geq 71$ as well.
Note that the largest label $\ell(v_{i,j})$ for $j=1,\ldots, 5$ is $6i-1$ for all $i$, hence the largest label for $Y_{5,n}$ is $6n-1$. Since we used the maximum of $2$ even labels on each pentagon along with the smallest possible odd labels, we have proven that $\pr(Y_{5,n})=6n-1$.
\end{proof}
For the graphs $Y_{3,n}$ and $Y_{5,n}$, the minimum coprime numbers were directly correlated to their independence number. This number is easy to obtain for stacked prisms involving larger odd cycles as well. Since $\alpha(C_{2k+1})=k$, one can observe that $\alpha(Y_{2k+1,n})=kn$. A minimum coprime labeling could use at most $kn$ even labels, forcing $(2k+1)n-kn=(k+1)n$ odd labels to be used, leading to the following conjecture.
\begin{conjecture}
The minimum coprime number for stacked $(2k+1)$-gon prism graph is
$$\pr(Y_{2k+1,n})=2(k+1)n-1.$$
\end{conjecture}
It should be noted to close this section that while we focused on the odd case, the stacked prisms with even-length cycles, $Y_{2k,n}$, satisfies $\alpha(Y_{2k,n})=kn=\frac{|V(Y_{2k,n})|}{2}$. Therefore, one would hope a prime labeling exists in this case, but this remains an open problem.
\section{Variation of generalized Petersen graphs}\label{GPvariation}
We extend the definition of the generalized Petersen graph for the case of even $n$ and $k=\frac{n}{2}$. We let $\GP^*(2k,k)$ denote this graph and use the same notation for the vertices $v_1,\ldots, v_{2k}$ and $u_1,\ldots, u_{2k}$ with edges $v_i v_{i+1}$, $v_i u_i$, and $u_i u_{i+k}$ where indices are calculated modulo $n$. Note that this graph differs from generalized Petersen graphs since $deg(u_i)=2$ for all $i=1,\ldots, n$ instead of the usual degree of $3$ for $\GP(n,k)$. For examples of minimum coprime labeling of $\GP^*(2k,k)$ with $k=9$ and $k=10$, see Figure~\ref{fig:gp2kk}.
\begin{theorem}
For the graph $\GP^*(2k,k)$ in which $k\geq 2$, we have the following:
\begin{enumerate}
\item $\GP^*(2k,k)$ is prime if $k$ is odd,
\item $\pr(\GP^*(2k,k))=4k+1$ if $k$ is even.
\end{enumerate}
\end{theorem}
\begin{proof}
We first assume $k$ is odd. We begin by labeling the vertices of $\GP^*(2k,k)$ as follows:
\begin{equation}\label{variation}
\ell(v_i)=\begin{cases}
4i-3, & \text{for $i=1,3,5,\ldots, k$;}\\
4i, & \text{for $i=2,4,6,\ldots, k-1$;}\\
4i-4k, &\text{for $i=k+1,k+3,k+5,\ldots, 2k$;}\\
4i-3-4k, &\text{for $i=k+2,k+4,k+6,\ldots, 2k-1$;}\\
\end{cases}
\end{equation}
\begin{equation*}
\ell(u_i)=\begin{cases}
4i-2, & \text{for $i=1,3,5,\ldots, k$;}\\
4i-1, & \text{for $i=2,4,6,\ldots, k-1$;}\\
4i-1-4k, &\text{for $i=k+1,k+3,k+5,\ldots, 2k$;}\\
4i-2-4k, &\text{for $i=k+2,k+4,k+6,\ldots, 2k-1$.}\\
\end{cases}
\end{equation*}
\begin{figure}[H]
\centering
\includegraphics[scale=1.1]{gp18-9.eps} \includegraphics[scale=1]{gp20-10.eps}
\caption{Examples of a prime labeling of $\GP^*(18,9)$ on the left and a minimum coprime labeling of $\GP^*(20,10)$ on the right.}
\label{fig:gp2kk}
\end{figure}
For the pairs $v_i v_{i+1}$ and $v_{i+k} v_{i+1+k}$ for $i\in\{1,\ldots,k-1\}$, it is clear that $\gcd(\ell(v_i),\ell(v_{i+1}))\in\{1,7\}$ and $\gcd(\ell(v_{i+k}),\ell(v_{i+k+1}))\in \{1,7\}$. Notice that $\gcd(\ell(v_{k}),\ell(v_{k+1}))=\gcd(4k-3,4)=1$ and $\gcd(\ell(v_{2k}),\ell(v_{1}))=\gcd(4k-1,1)=1$. For the edges $u_i u_{i+k}$, it is easily verified that when $i\in\{1,3,\ldots,k\}$,
\[
\gcd(\ell(u_i),\ell(u_{i+k}))=\gcd(4i-2,4(i+k)-1-4k) = \gcd(4i-2,4i-1)=1.
\]
Similarly, $\gcd(\ell(u_i),\ell(u_{i+k}))=1$ when $i\in\{2,4,\ldots,k-1\}$ and $\gcd(\ell(u_i),\ell(v_i)) = 1$ for all $i=1,\ldots, 2k$ since these pairs are consecutive integers. Thus, our only concern with the labeling is when $\ell(v_i)$ and $\ell(v_{i+1})$ are both divisible by 7.
We handle these instances by breaking the proof into several cases based on the remainder of $\ell(v_i)/3$ and whether or not $5$ divides $\ell(v_i)+2$. For the sake of simplicity, let $\ell(v_i)=a$ where $i\in\{1,3,\ldots,k-2, k+2, k+4,\ldots, 2k-1\}$.
Notice that in our labeling, $\ell(v_i)=a$ is odd in these cases in which $\ell(v_{i+1})-\ell(v_i)=7$.
In each of the cases below, we are assuming that $a\equiv 0 \pmod{7}$.
\bigskip
\noindent \textbf{Case 1:} Suppose that $a\equiv 1\pmod{3}$.
In this case, swap the labels $a$ and $a-2$ on the vertices $v_i$ and $u_{i-1}$. Since $a$ is not divisible by~$3$, $\gcd(a-3,a)=1$. Since $a-2$ is also not divisible by 3, $\gcd(a-2,a+7)=\gcd(a-2,a+1)=1$. Thus, the two labels involved in the swap are relatively prime with all adjacent labels.
\bigskip
\noindent \textbf{Case 2:} Suppose that $a\equiv 0\pmod{3}$ and $5 \nmid a$.
In this case, swap the labels $a+5$ and $a+7$ on the vertices $v_{i+1}$ and $u_{i+1+k}$. Since $a$ is not divisible by $5$, $\gcd(a,a+5)=1$. Since both $a+5$ and $a+7$ are not divisible by $3$, $\gcd(a+5,a+8)=\gcd(a+4,a+7)=1$.
Thus, all newly adjacent pairs of labels after making this swap are relatively prime.
\bigskip
\noindent \textbf{Case 3:} Suppose that $a\equiv 0\pmod{15}$.
The labels $a-1,a,a+1,a+5,a+6,a+7$ will be relabeled as $a+7,a+6,a+5,a-1,a,a+1$, respectively. Based on the placement of the swapped labels, we only need to check the $\gcd$ between six newly adjacent pairs of labels. Since $a$ is a multiple of $3$, $5$, and $7$, we have
\[
\gcd(a+1,a+8)=\gcd(a-1,a+4)=\gcd(a+2,a+5)=\gcd(a-2,a+7)=\gcd(a+1,a+6)=1.
\]
Note that if $i=2k-1$, instead of the label $a+8$, we have label $1$ on $v_{i+2}$, which is still relatively prime with $a+1$.
Our last remaining pair of adjacent labels involves $a+7$, which is now adjacent to a vertex labeled $a-8$. Since $a\equiv 0\pmod{15}$, $\gcd(a-8,a+7)=1$. Therefore, the reassigned labels are relatively prime with any newly adjacent label.
\bigskip
\noindent \textbf{Case 4:} Suppose that $a\equiv 2\pmod{3}$ and $5 \nmid a+2$.
In this case, swap the labels $a$ and $a+2$. Since both $a$ and $a+2$ are not divisible by $3$ and $a+2$ is not divisible by $5$, it follows that
\[
\gcd(a,a+3) = \gcd(a+2,a+7) = \gcd(a-1,a+2)=1.
\]
Hence any new adjacencies after the swap consist of relatively prime labels.
\bigskip
\noindent \textbf{Case 5:} Suppose that $a\equiv 2\pmod{3}$ and $5\mid a+2$.
The labels $a,a+1,a+2,a+6,a+7,a+8$ are reassigned as $a+6,a+7,a+8,a+2,a+1,a$, respectively. Based on the placement of the swapped labels, as in Case 3, we need only check the $\gcd$ of six pairs of labels. Since $a\equiv 2\pmod{3}$, $a+2\equiv 0\pmod{5}$, and $a\equiv 0\pmod{7}$,
\[
\gcd(a-1,a+6)=\gcd(a+3,a+8)=\gcd(a+2,a+5)=\gcd(a+1,a+6)=\gcd(a,a+9)=1.
\]
If $\ell(v_{i+2})=a+8$ in the original labeling of the vertices, then since $a$ is odd, $a\equiv 2\pmod{3}$, and $a+2\equiv 0\pmod{5}$, it follows that $\gcd(a+15,a)=1$.
Since $k$ is odd, it is not possible for $\ell(v_{i+2})$ to be $4$.
It is possible that $\ell(v_{i+2})=1$ in the case of $i=2k-1$, but in this case, $\ell(v_{i+3})=8$ and the label~$a$ is adjacent to $8$, which again proves our claim.
Thus, all new pairs of adjacent labels are relatively prime.
Combining all five cases, we have proven that $\pr(\GP^*(2k,k))=4k$ and hence $\GP^*(2k,k)$ is prime for all odd $k$.
Now suppose that $k$ is an even integer. To show that $\GP^*(2k,k)$ is not prime when $k$ is even, we consider the independence number $\alpha(\GP^*(2k,k))$. An independent set can contain at most $k$ vertices from the $k$-cycle formed by the vertices $v_1,\ldots, v_{2k}$, either the set of vertices with odd indices or the set with even indices. Without loss of generality, consider the independent set $\{v_1,v_3,\ldots, v_{2k-1}\}$. Since we have edges $u_i v_i$ for all $i$, only vertices of the form $u_{2j}$ can be added to the independent set. However, the edges $u_i u_{i+k}$ prevent all $k$ of those edges from being independent. Thus, the size of our independent set is less than $2k$ if $k$ of the vertices $v_1,\ldots, v_{2k}$ are included. If we instead begin with fewer than $k$ of these vertices in an independent set, we cannot use more than $k$ vertices from $u_1,\ldots, u_{2k}$ since only one of $u_i$ or $u_{i+k}$ can be included for each $i=1,\ldots, k$. Hence we cannot create an independent set of size $2k$, showing that $\alpha(\GP^*(2k,k))<2k=\frac{1}{2}|V|$. Therefore, by Lemma~\ref{ind}, this graph is not prime when $k$ is even.
We then create a minimum coprime labeling when $k$ is even by starting with a labeling $\ell$ similar our odd case, defined by the following:
\begin{equation}\label{variationeven}
\ell(v_i)=\begin{cases}
4i-3, & \text{for $i=1,3,5,\ldots, k-1$;}\\
4i, & \text{for $i=2,4,6,\ldots, k-2$;}\\
4i-4k, &\text{for $i=k+1,k+3,k+5,\ldots, 2k-1$;}\\
4i-3-4k, &\text{for $i=k+2,k+4,k+6,\ldots, 2k$;}\\
\end{cases}
\end{equation}
\begin{equation*}
\ell(u_i)=\begin{cases}
4i-2, & \text{ for $i=1,3,5,\ldots, k-1$;}\\
4i-1, & \text{ for $i=2,4,6,\ldots, k$;}\\
4i-1-4k, &\text{ for $i=k+1,k+3,k+5,\ldots, 2k-1$;}\\
4i-2-4k, &\text{ for $i=k+2,k+4,k+6,\ldots, 2k$.}\\
\end{cases}
\end{equation*}
Note that the label for $v_k$ was not listed in Equation~\eqref{variationeven} since continuing the pattern $\ell(v_{i})=4i$ for even $i$ would assign it as $\ell(v_{k})=4k$, which is not relatively prime with its neighboring label $\ell(v_{k+1})=4$. Hence we instead assign $\ell(v_{k})$ to be $4k+1$, which we observe is relatively prime with the adjacent labels since $\gcd(4,4k+1)=\gcd(4k-1,4k+1)=\gcd(4k-7,4k+1)=1$.
We note by similar reasoning to the odd case that our labeling when $k$ is even is coprime with the exception of some adjacent vertices $v_i v_{i+1}$ whose labels share a common factor of $7$. We proceed by making the same alterations to $\ell$ as described in Cases 1--5, which by analogous arguments to those made in the odd $k$ case results in a coprime labeling if the label $\ell(v_k)$ and its neighbors are not involved in the alterations to $\ell$. The only situation in which any of the five cases involve swapping these labels would be if $a=\ell(v_{k-1})$. However, with $\ell(v_k)=4k+1$, we have $\ell(v_k)-\ell(v_{k-1})=8$, so these labels cannot share a common factor of $7$. Hence we have shown this is a coprime labeling for the case of even $k$ with largest label $4k+1$. Therefore, since the graph is not prime in this case, we have proven $\pr(\GP^*(2k,k))=4k+1$.
\end{proof}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
\providecommand{\MRhref}[2]{
\href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\appendix
\section{Additional generalized Petersen results}\label{additional}
For Theorems~\ref{n+4}--\ref{n+6}, the proof for why the labeling is a coprime labeling is omitted as the pattern is clearly given in the tables and can be verified in each case. The techniques used are all outlined in Observation~\ref{easy}. Recall that we are working under the assumption that $n$ is odd for the following theorems.
\begin{theorem}\label{n+4}
If $n+4$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We may assume $n\not\equiv 2\pmod{3}$, otherwise $n+4$ would be divisible by 3 and hence not prime.
If $n\equiv 0\pmod{3}$, then we use the labeling defined in Table~\ref{tab:n+4}.
If $n\equiv 1\pmod{3}$, then we alter the previous labeling and instead use the labeling defined in Table~\ref{tab:n+4b}.
\end{proof}
\begin{theorem}\label{n-2}
If $n-2$ is prime and $n>5$, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We may assume $n\not\equiv 2\pmod{3}$ to avoid $n-2$ being a multiple of 3. If $n\equiv 0\pmod{3}$, then we use the labeling defined in Table~\ref{tab:n-2}. If $n\equiv 1\pmod{3}$, we instead label the graph using the labeling in Table~\ref{tab:n-2b}. Note that in both cases, the labels on most edges $u_i v_i$ are relatively prime since the difference of the labels is the prime $n-2$, but a swap is necessary to avoid both labels being multiples of that prime number.
\end{proof}
\begin{theorem}\label{n-4}
If $n-4$ is prime and $n>7$, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We may assume $n\not\equiv 1\pmod{3}$, else $n-4$ is a multiple of 3.
If $n\equiv 0\pmod{3}$, then we use the labeling defined in Table~\ref{tab:n-4}.
If $n\equiv 2\pmod{3}$, then use the same labeling defined in Table~\ref{tab:n-4b}.
\end{proof}
\begin{theorem}\label{2n+3}
If $2n+3$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We may assume $n\not\equiv 0\pmod{3}$ to avoid $2n+3$ being divisible by $3$.
If $n\equiv 1\pmod{3}$, then we use the labeling defined in Table~\ref{tab:2n+3}.
If $n\equiv 2\pmod{3}$, then use the same labeling defined in Table~\ref{tab:2n+3b} except $n+1$ is labeled as $n-1$ instead.
\end{proof}
\begin{theorem}\label{2n-3}
If $2n-3$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We may assume $n\not\equiv 0\pmod{3}$, otherwise $2n-3$ is a multiple of $3$.
If $n\equiv 2\pmod{3}$, then we use the labeling defined in Table~\ref{tab:2n-3}.
If $n\equiv 1\pmod{3}$, then we use the labeling defined in Table~\ref{tab:2n-3b}.
\end{proof}
\begin{theorem}\label{2n-5}
If $2n-5$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We may assume $n\not\equiv 1\pmod{3}$ to avoid $3$ dividing into $2n-5$.
If $n\equiv 0$ or $2\pmod{3}$ and $n\equiv 1,2,$ or $4\pmod{5}$, then we use the labeling defined in Table~\ref{tab:2n-5}.
When $n\equiv 0$ or $2\pmod{3}$ and $n\equiv 0\pmod{5}$, then $2n-5\equiv 0\pmod{5}$, so we ignore these cases.
When $n\equiv 0\pmod{3}$ and $n\equiv 3\pmod{5}$, then we use the labeling defined in Table~\ref{tab:2n-5b}.
When $n\equiv 2\pmod{3}$ and $n\equiv 3\pmod{5}$, then we use the labeling defined in Table~\ref{tab:2n-5c}.
\end{proof}
\begin{theorem}\label{n+6}
If $n+6$ is prime, then $\pr(\GP(n,1))=2n+1$.
\end{theorem}
\begin{proof}
We may assume that $n\not\equiv 0\pmod{3}$, otherwise $n+6$ is divisible by 3.
If $n\equiv 1$ or $2\pmod{3}$ and $n\equiv 0,2,$ or $3\pmod{5}$, then we use the labeling defined in Table~\ref{tab:n+6}.
If $n\equiv 2\pmod{3}$ and $n\equiv 1\pmod{5}$, then we use the labeling defined in Table~\ref{tab:n+6b}.
If $n\equiv 1 \pmod{3}$ and $n\equiv 1\pmod{5}$, then we use the labeling defined in Table~\ref{tab:n+6c}.
If $n\equiv 1$ or $2\pmod{3}$ and $n\equiv 4\pmod{5}$, then $n+6$ is divisible by 5, so these cases are removed.
\end{proof}
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
1& 2 & $\cdots$ & $n-3$ & $n-2$ & $n-1$ & $n$ \\
\hline
$n+5$ & $n+6$ & $\cdots$ & $2n+1$ & $n+1$ & $n+2$ & $n+4$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{n+4} when $n\equiv 0\pmod{3}$}
\label{tab:n+4}
\vspace{.2in}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
1& 2 & $\cdots$ & $n-3$ & $n-2$ & $n+2$ & $n+1$ \\
\hline
$n+5$ & $n+6$ & $\cdots$ & $2n+1$ & $n$ & $n+3$ & $n+4$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{n+4} when $n\equiv 1\pmod{3}$}
\label{tab:n+4b}
\vspace{.2in}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & $\cdots$ & $n-3$ & $n-2$ & $n-1$ & $n$ \\
\hline
$2n-1$ & $2n+1$ & $n+1$ & $n+2$ & $\cdots$ & $2n-5$ & $2n-2$ & $2n-3$ & $2n-4$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{n-2} when $n\equiv 0\pmod{3}$}
\label{tab:n-2}
\vspace{.2in}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & $\cdots$ & $n-5$ & $n-4$ & $n-3$ & $n-2$ & $n-1$ & $n$ \\
\hline
$2n-1$ & $2n+1$ & $n+1$ & $n+2$ & $\cdots$ & $2n-7$ & $2n-4$ & $2n-5$ & $2n-6$ & $2n-3$ & $2n-2$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{n-2} when $n\equiv 1\pmod{3}$}
\label{tab:n-2b}
\end{table}
\clearpage
\begin{table}[H]
\resizebox{\textwidth}{!}{
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & 5 & 6 & $\cdots$ & $n-7$ & $n-6$ & $n-5$ & $n-4$ & $n-3$ & $n-2$ & $n-1$ & $n$ \\
\hline
$2n-3$ & $2n-1$ & $2n-2$ & $2n+1$ & $n+1$ & $n+2$ & $\cdots$ & $2n-11$ & $2n-8$ & $2n-9$ & $2n-10$ & $2n-7$ & $2n-6$ & $2n-5$ & $2n-4$ \\
\hline
\end{tabular}}
\caption{Labeling for Theorem~\ref{n-4} when $n\equiv 0\pmod{3}$}
\label{tab:n-4}
\vspace{.2in}
\resizebox{\textwidth}{!}{
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & 5 & 6 & $\cdots$ & $n-5$ & $n-4$ & $n-3$ & $n-2$ & $n-1$ & $n$ \\
\hline
$2n-3$ & $2n-1$ & $2n$ & $2n+1$ & $n+1$ & $n+2$ & $\cdots$ & $2n-9$ & $2n-6$ & $2n-7$ & $2n-8$ & $2n-5$ & $2n-4$ \\
\hline
\end{tabular}}
\caption{Labeling for Theorem~\ref{n-4} when $n\equiv 2\pmod{3}$}
\label{tab:n-4b}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & $\cdots$ & $n-2$ & $n+1$ & $n+2$ \\
\hline
$n$ & $2n+1$ & $2n$ & $2n-1$ & $\cdots$ & $n+5$ & $n+4$ & $n+3$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{2n+3} when $n\equiv 1\pmod{3}$}
\label{tab:2n+3}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & $\cdots$ & $n-2$ & $n$ & $n+3$ \\
\hline
$n-1$ & $2n+1$ & $2n$ & $2n-1$ & $\cdots$ & $n+5$ & $n+4$ & $n+2$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{2n+3} when $n\equiv 2\pmod{3}$}
\label{tab:2n+3b}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & $\cdots$ & $n-2$ & $2n-3$ & $2n$ \\
\hline
$2n-2$ & $2n-5$ & $2n-6$ & $2n-7$ & $\cdots$ & $n-1$ & $2n-1$ & $2n+1$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{2n-3} when $n\equiv 2\pmod{3}$}
\label{tab:2n-3}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & 4 & $\cdots$ & $n-2$ & $2n$ & $2n+1$ \\
\hline
$2n-4$ & $2n-5$ & $2n-6$ & $2n-7$ & $\cdots$ & $n-1$ & $2n-3$ & $2n-1$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{2n-3} when $n\equiv 1\pmod{3}$}
\label{tab:2n-3b}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & $\cdots$ & $n-3$ & $2n-5$ & $2n+1$ & $2n$ \\
\hline
$2n-6$ & $2n-7$ & $2n-8$ & $\cdots$ & $n-2$ & $2n-3$ & $2n-2$ & $2n-1$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{2n-5} when $n\equiv 0,2\pmod{3}$ and $n\equiv 1,2,$ or $4\pmod{5}$ }
\label{tab:2n-5}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & $\cdots$ & $n-3$ & $2n-5$ & $2n-1$ & $2n$ \\
\hline
$2n-4$ & $2n-7$ & $2n-8$ & $\cdots$ & $n-2$ & $2n-3$ & $2n-2$ & $2n+1$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{2n-5} when $n\equiv 0\pmod{3}$ and $n\equiv 3\pmod{5}$}
\label{tab:2n-5b}
\end{table}
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & $\cdots$ & $n-3$ & $2n-5$ & $2n-1$ & $2n$ \\
\hline
$2n-6$ & $2n-7$ & $2n-8$ & $\cdots$ & $n-2$ & $2n+1$ & $2n-2$ & $2n-3$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{2n-5} when $n\equiv 2\pmod{3}$ and $n\equiv 3\pmod{5}$}
\label{tab:2n-5c}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & $\cdots$ & $n-5$ & $n-4$ & $n-3$ & $n-2$ & $n+2$ & $n+3$ \\
\hline
$n+7$ & $n+8$ & $n+9$ & $\cdots$ & $2n+1$ & $n+1$ & $n$ & $n-1$ & $n+4$ & $n+6$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{n+6} when $n\equiv 1$ or $2\pmod{3}$ and $n\equiv 0,2,$ or $3\pmod{5}$}
\label{tab:n+6}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & $\cdots$ & $n-5$ & $n-4$ & $n-3$ & $n-2$ & $n+2$ & $n+5$ \\
\hline
$n+7$ & $n+8$ & $n+9$ & $\cdots$ & $2n+1$ & $n+1$ & $n$ & $n+3$ & $n+4$ & $n+6$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{n+6} when $n\equiv 2\pmod{3}$ and $n\equiv 1\pmod{5}$}
\label{tab:n+6b}
\vspace{.2in}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1& 2 & 3 & $\cdots$ & $n-5$ & $n-4$ & $n-3$ & $n-2$ & $n+4$ & $n+5$ \\
\hline
$n+7$ & $n+8$ & $n+9$ & $\cdots$ & $2n+1$ & $n+1$ & $n$ & $n+3$ & $n+2$ & $n+6$ \\
\hline
\end{tabular}
\caption{Labeling for Theorem~\ref{n+6} when $n\equiv 1\pmod{3}$ and $n\equiv 1\pmod{5}$}
\label{tab:n+6c}
\end{table}
\begin{thebibliography}{99}
\bibitem{AF}
J. Asplund and N. B. Fox, Minimum coprime labelings for operations on graph, \emph{Integers} \textbf{19} (2019), Article A24.
\bibitem{BHM}
B. Behsaz, P. Hatami, and E. Mahmoodian, On minimum vertex covers of generalized Petersen graph, \emph{Australas. J. Combin.} \textbf{40} (2008), 253--264.
\bibitem{Berliner}
A. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, and C. McBee, Coprime
and prime labelings of graphs, \emph{J. Integer Sequences} \textbf{19}
(2016), \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Mbirika/mbi3.html}{Article 16.5.8}.
\bibitem{BEA}
N. Besharati, J. B. Ebrahimi, and A. Azadi, Independence number of generalized Petersen graphs, \emph{Ars Combin.} \textbf{124} (2016), 239--255.
\bibitem{dean}
N. Dean, Proof of the prime ladder conjecture, \emph{Integers} \textbf{17} (2017), Article A40.
\bibitem{FGS}
J. Fox, R. Gera, and P. St\u{a}nic\u{a}, The independence number for the generalized Petersen graphs, \emph{Ars Combin.} \textbf{103} (2012), 439--451.
\bibitem{FH}
H.-L. Fu and K.-C. Huang, On prime labelling, \emph{Discrete Math.} \textbf{127} (1994), 181--186.
\bibitem{Gallian}
J. A. Gallian, A dynamic survey of graph labeling, \emph{Electron. J. Combin.} \textbf{DS6} (2020).
\bibitem{HLYZ}
K. Haque, X. Lin, Y. Yang, and P. Zhao, On the prime labeling of generalized Petersen graph $P(n,1)$, \emph{Util. Math.} \textbf{83} (2010), 95--106.
\bibitem{HLYZ2}
K. Haque, X. Lin, Y. Yang, and P. Zhao, On the prime labeling of
generalized Petersen graphs $P(n,3)$, \emph{Int. J. Contemp. Math. Sci.}
\textbf{6} (2011), 1783--1800.
\bibitem{Lee}
C. Lee, Minimum coprime graph labelings, \emph{J. Integer Sequences}
\textbf{23} (2020), \href{https://cs.uwaterloo.ca/journals/JIS/VOL23/Lee/lee7.html}{Article 20.11.4}.
\bibitem{PG}
U. Prajapati and S. Gajjar, Prime labeling of generalized Petersen graph, \emph{Internat. J. of Math. and Soft Comput.} \textbf{5} (2015), 65--71.
\bibitem{SSCEHRW}
S. Schluchter, J. Schroeder, K. Cockus, R. Ellingson, H. Harris, E. Rarity, and T. Wilson, Prime labelings of generalized Petersen graphs, \emph{Involve} \textbf{10} (2017), 109--124.
\bibitem{TDH}
A. Tout, A. N. Dabboucy, and K. Howalla, Prime labeling of graphs, \emph{Nat. Acad. Sci. Lett.} \textbf{11} (1982), 365--368.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05C78, Secondary 11A05.
\noindent \emph{Keywords: } coprime labeling, prime labeling, generalized Petersen graph, prism graph.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 22 2020;
revised version received February 10 2021; February 14 2021.
Published in {\it Journal of Integer Sequences},
February 15 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}