# Odd Prime Graph Labelings

Holly Carter
Austin Peay State University
<EMAIL_ADDRESS>

N. Bradley Fox
Austin Peay State University
<EMAIL_ADDRESS>

###### Abstract

An odd prime labeling is a variation of a prime labeling in which the vertices
of a graph of order $n$ are labeled with the distinct odd integers $1$ to
$2n-1$ so that the labels of adjacent vertices are relatively prime. This
paper investigates many different classes of graphs including disjoint unions
of cycles, stacked prisms, and particular types of caterpillars, by using
various methods to construct odd prime labelings. We also demonstrate progress
toward proving a conjecture that all prime graphs have an odd prime labeling.

##  1 Introduction

Consider a simple graph $G$ of order $n$. A prime labeling of $G$ is an
assignment of the integers $1$ to $n$ as labels of the vertices such that the
labels of each adjacent pair of vertices are relatively prime. A graph with
such a labeling is called prime. This labeling was conceived by Entringer and
first introduced by Tout, Dabboucy, and Howalla [19]. By changing the labeling
set or altering the relatively prime condition, many variations of prime
labelings have since been developed, such as minimum coprime labelings [1, 2,
3, 11], neighborhood-prime labelings [4, 14], and $k$-prime labelings [20]. An
overview of results on prime labelings and these variations can be found in
the survey by Gallian [9].

One of the more recently studied variations is the odd prime labeling [13,
21], which consists of labeling the vertices with the set of odd integers
$\\{1,3,\ldots,2n-1\\}$ such that adjacent pairs of vertices have relatively
prime labels. We use the term odd prime to describe graphs that can be labeled
in this manner. A function $\ell$ will often be used as notation to describe
the labeling as an injective map from the vertices $V$ to the set
$\\{1,3,\ldots,2n-1\\}$. To be odd prime, we need $\gcd(\ell(u),\ell(v))=1$
for all adjacent vertices $u$ and $v$. The first papers to introduce this
labeling demonstrated a variety of classes of graphs are odd prime, including
all paths, cycles, ladders, wheels, and the class of generalized Petersen
graphs $GP(n,2)$ [13], as well as helms and disjoint unions of two cycles
[21]. Furthermore, characterizations for when complete graphs and complete
bipartite graphs are odd prime are given in [21].

In this paper we continue the exploration of which classes of graphs admit an
odd prime labeling. We first introduce some lemmas and observations in Section
2 that will aid in developing our labelings or determining that an odd prime
labeling cannot exist. In Section 3 we investigate a wide array of graphs
created through combining cycles such as the disjoint union of cycles, snake
graphs, book graphs, and stacked prisms. Section 4 shifts our focus to the
large class of connected graphs without cycles known as trees, in which we
introduce labelings for spiders, perfect binary trees, special cases of
caterpillars, and firecrackers. In Section 5 we fully characterize when odd
prime labelings exist for powers of paths and cycles. Finally, Section 6
consists of progress towards proving the conjecture that all prime graphs are
also odd prime.

##  2 Preliminary Material

The following lemmas summarize a few results by Youssef and Almoreed [21]
involving properties of odd prime graphs.

######  Lemma 1.

If $G$ is an odd prime graph, then every spanning subgraph of $G$ is also odd
prime.

We use $\beta(G)$ to denote the independence number of a graph $G$, defined as
the size of the largest set of vertices that is independent, meaning no edge
exists between any pair of vertices in said set.

######  Lemma 2.

The independence number of any odd prime graph $G$ of order $n$ satisfies

$\beta(G)\geq\left\lfloor\frac{n+1}{3}\right\rfloor.$

The lower bound of the previous inequality corresponds to the number of
multiples of $3$ in the sequence of odd labels $1,3,\ldots,2n-1$. Therefore,
it provides a useful condition to demonstrate a graph is not odd prime if one
can show $\beta(G)<\lfloor\frac{n+1}{3}\rfloor$ since in this case, there
would not be enough independent vertices to place those multiples of $3$. This
is analogous to the requirement for prime graphs in which
$\beta(G)\geq\lfloor\frac{n}{2}\rfloor$ where this relates to the placement of
even labels from the sequence $1,2,\ldots,n$.

The following properties of the $\gcd$ of two integers will be very useful in
proving our labelings are odd prime. Labels that differ by a positive power of
two will be particularly helpful in many of our upcoming results and hence
will be used without citation at times.

######  Observation 3.

For any non-zero integers $a$, $b$, and $t$ and any positive integer $k$, the
following hold:

  1. (i)

$\gcd(a,a+2^{k})=1$ if $a$ is odd,

  2. (ii)

$\gcd(a,b)=\gcd(a,a-b)$,

  3. (iii)

$\gcd(a,b)=\gcd(a+tb,b)$.

##  3 Combinations of Cycles

We being our investigation of graphs with odd prime labelings by considering
various ways of combining cycles. First, we examine the disjoint union of
cycles of any length, in which the disjoint union of two graphs is formed by
taking the union of the vertex sets and the edge sets. It was shown in [21]
that the disjoint union $C_{m}\cup C_{n}$ is odd prime for any $m,n\geq 3$. It
is noteworthy that in the case of prime labelings, the disjoint union of
cycles is not prime if both $m$ and $n$ are odd, which is a condition that
does not carry over into odd prime labelings. Furthermore, when generalized to
the union of more than two cycles, Deretsky et al. [6] showed many cases of
these disjoint unions to be prime if at most one odd cycle is included in the
disjoint union. However, it is ultimately still an open conjecture whether the
disjoint union of any number of even cycles is always prime. The following
result proves the odd prime analog of this conjecture while also removing the
restriction on the number of cycles being odd. An example of a disjoint union
of four cycles of various lengths with an odd prime labeling is shown in
Figure 1.

######  Theorem 4.

All disjoint unions of cycles, $\bigcup_{i=1}^{n}C_{k_{i}}$, are odd prime for
any lengths $k_{i}$ and any number of cycles $n$.

###### Proof.

We will label the cycles sequentially from $C_{k_{1}}$ to $C_{k_{n}}$. Given a
cycle $C_{k}$ consider the vertices in clockwise order as
$v_{1},v_{2},\ldots,v_{k}$. Let $m$ be the smallest unused odd label. We
create our labeling $\ell$ starting with $\ell(v_{1})$ in a pattern in which
we alternate between the clockwise and counter-clockwise paths around the
cycle.

If $k$ is even, label the sequence of vertices

$v_{1},v_{k},v_{2},v_{k-1},v_{3},v_{k-2},\ldots,v_{\frac{k}{2}},v_{\frac{k}{2}+1}$

with the labels $m,m+2,\ldots,m+2k-2$, respectively. The vertices on edges
$v_{1}v_{k}$ and $v_{\frac{k}{2}}v_{\frac{k}{2}+1}$ will be labeled with
consecutive odd integers. All of the other adjacent labels will differ by $4$.

If $k$ is odd, we similarly label the sequence of vertices

$v_{1},v_{k},v_{2},v_{k-1},v_{3},v_{k-2},\ldots,v_{\frac{k+1}{2}-1},v_{\frac{k+1}{2}+1},v_{\frac{k+1}{2}}$

with $m,m+2,\ldots,m+2n-2$, respectively. The labels of the adjacent vertices
again differ by $2$ or $4$. Then by Observation 3 $(i)$, adjacent labels in
both cases are relatively prime. Thus all disjoint unions of cycles,
$\bigcup_{i=1}^{n}C_{k_{i}}$, are odd prime for any lengths $k_{i}$ and any
number of cycles $n$. ∎

Figure 1: An odd prime labeling of a disjoint union of cycles $C_{5}\cup
C_{8}\cup C_{3}\cup C_{4}$

We will now consider snake graphs, which are denoted as $S_{k,n}$ where $k$
represents the length of the cycles attached along a path of $n$ vertices.
Figure 2 includes an odd prime labeling of a snake graph with hexagon cycles.
The vertices along the path will be represented as $v_{i}$ with $i=1$ to $n$.
The cycles are formed by adjoining paths
$v_{i},w_{i,1},w_{i,2},\ldots,w_{i,k-2},v_{i+1}$ for each $i=1$ to $n-1$.
Snake graphs were indirectly shown to be prime in [17] where a related graph
called the star$(m,n)$-gon was proven to be prime. We now show the analogous
is true for them being odd prime.

######  Theorem 5.

Snake graphs $S_{k,n}$ are odd prime for any $k\geq 3$ and $n\geq 2$.

###### Proof.

Note that there are $(k-1)(n-1)+1$ vertices, so the largest label that we will
use is $2(k-1)(n-1)+1$. We create our labeling function $\ell$ by assigning
labels sequentially from 1 to $2(k-1)(n-1)+1$ to the following sequence of
vertices:

$v_{1},w_{1,1},w_{1,2},\ldots,w_{1,k-2},v_{2},\ldots,v_{n-1},w_{n-1,1},w_{n-1,2},\ldots,w_{n-1,k-2},v_{n}.$

The vertex pairs $w_{i,j}w_{i,j+1}$, as well as $v_{i}w_{i,1}$ and
$w_{i,k-2}v_{i+1}$, will have relatively prime labels because they are labeled
with consecutive odd integers. Therefore, the only pairs of labels that we
have to confirm are relatively prime are on the vertices $v_{i}$ and
$v_{i+1}$, where we note $\ell(v_{i})=2(k-1)(i-1)+1$. By Observation 3 $(ii)$
for the second equality and $(iii)$ with $t=-i$ for the third equality, we
have

$\displaystyle\gcd(\ell(v_{i+1}),\ell(v_{i}))$
$\displaystyle=\gcd(2(k-1)i+1,2(k-1)(i-1)+1)$
$\displaystyle=\gcd(2(k-1)i+1,2(k-1))$ $\displaystyle=\gcd(1,2(k-1))$
$\displaystyle=1.$

Thus all snake graphs $S_{k,n}$ are odd prime. ∎

Figure 2: An odd prime labeling of the snake graph $S_{6,5}$

Our next class of graphs is similar to snake graphs in that $n$ cycles of
length $k$ are linked together by shared vertices, but informally, they are
glued together in the middle of the cycle instead of forming a path along
their bases. Cycle chains, denoted as $\mathcal{C}_{k}^{n}$, will be defined
depending on the parity of the cycle length $k$. For even $k$, we begin with
vertices $v_{1},v_{2},\ldots,v_{n+1}$ and form the following two paths between
each pair: $v_{i},w_{i,1},w_{i,2},\ldots,w_{i,\frac{k}{2}-1},v_{i+1}$ and
$v_{i},x_{i,1},x_{i,2},\ldots,x_{i,\frac{k}{2}-1},v_{i+1}$. When $k$ is odd,
we create the cycles in $\mathcal{C}_{k}^{n}$ in similar fashion, but the
$w$-path will be one edge shorter than the $x$-path. Specifically, we join the
vertices $v_{i}$ and $v_{i+1}$ with the paths
$v_{i},w_{i,1},w_{i,2},\ldots,w_{i,\frac{k-1}{2}-1},v_{i+1}$ and
$v_{i},x_{i,1},x_{i,2},\ldots,x_{i,\frac{k-1}{2}},v_{i+1}$. See Figure 3 for
an example of a cycle chain with an odd prime labeling. Cycle chains,
particularly in the case of even length cycles, were examined for prime
labelings in [7] where they were shown to be prime in certain cases, but we
conclude in the next result that all cycle chains have an odd prime labeling.

Figure 3: An odd prime labeling of the cycle chain graph $C_{5}^{4}$

######  Theorem 6.

Cycle chains, $\mathcal{C}_{k}^{n}$, are odd prime for all $k\geq 3$ and
$n\geq 1$.

###### Proof.

We start by labeling $v_{1}$ with $1$ and then follow a similar alternating
pattern as in the labeling of the disjoint union of cycles. If the cycle is
even, we then label the vertices in this pattern for all $1\leq i\leq n$ :

$w_{i,1},x_{i,1},w_{i,2},x_{i,2},\ldots,w_{i,\frac{k}{2}-1},x_{i,\frac{k}{2}-1},v_{i+1}$

with the odd integers $1,3,\ldots,2nk-2n+1$. If the cycle is odd, label the
vertices as follows for all $1\leq i\leq n$:

$x_{i,1},w_{i,1},x_{i,2},w_{i,2},\ldots,w_{i,\frac{k-3}{2}},x_{i,\frac{k-1}{2}},v_{i+1}$

with the odd labels $1,3,\ldots,2nk-2n+1$. Since every difference between the
labels of adjacent vertices will be 2 or 4, all cycle chains are odd prime. ∎

We next examine the book graph $B_{n,k}$, defined as $n$ cycles each with $k$
vertices that all share a common edge. Each cycle is referred to as a page of
the book graph. We call the vertices of the shared edge $u$ and $v$. Let
$w_{i,j}$ be the vertices in the $i$th page with $j$ being the clockwise
position within each cycle, such that $u$ is adjacent to each $w_{i,1}$ and
$v$ is adjacent to $w_{i,k-2}$. Figure 4 includes a book graph featuring
hexagonal pages with an odd prime labeling. This particular class of graphs
was shown to be prime in [17] for the case of square pages or $k=4$. We now
prove the broader result that book graphs are odd prime for any size or number
of pages.

Figure 4: An odd prime labeling of the book graph $B_{3,6}$

######  Theorem 7.

Book graphs $B_{n,k}$ are odd prime for any $n\geq 1$ and $k\geq 3$.

###### Proof.

We first assign $\ell(u)=1$, and then label the sequence of vertices in the
first page $s_{1,1}$ to $s_{1,k-2}$ with $3,5,\ldots,2k-3$, respectively.
Continue the pattern of using the next $k-2$ odd integers to label the
subsequent pages from $i=2$ to $n$. This leaves the vertex $v$ to be labeled
as the next available odd integer so that $\ell(v)=2(k-2)n+3$.

After this initial labeling, the current label of $v$ may share a common
factor with the label of one or more of the vertices $\ell(w_{i,k-2})$ for
some $i$. Therefore, we will appeal to Bertrand’s postulate, which states for
any integer $t>1$, there always exists at least one prime number $p$ with
$t<p<2t$. Thus, considering $t$ to be the number of vertices in $B_{n,k}$,
which is $(k-2)n+2$, we can guarantee that there will be a prime $p$ such that
$(k-2)n+2<p<2(k-2)n+4$. This means that we have already used this prime number
within our labeling. If $p=2(k-2)n+3$, then we can leave this as the label of
$v$. Otherwise, $\ell(w_{a,b})=p$ for some particular $a$ and $b$, so we
reassign $\ell(v)=p$ and shift the labels on page $a$ so that
$\ell(w_{a,k-2})=2(k-2)n+3$ and each $\ell(w_{a,j})$ for $j=b$ to $k-3$ is
assigned the original label of $w_{a,j+1}$.

We clearly have that $\gcd(\ell(u),\ell(w_{i,1}))=1$ since $\ell(u)=1$. Since
$p$ is a prime number that is large enough so that $2p$ is greater than any
other label on the graph, $\gcd(\ell(v),\ell(w_{i,k-2}))=1$ as well. The
labels on vertices $w_{a,b-1}$ and $w_{a,b}$ differ by $4$ after the labeling
shift has been made, and all adjacent pairs of the form $w_{i,j}$, $w_{i,j+1}$
have labels that are consecutive odd integers. Thus, our labeling of the book
graph $B_{n,k}$ is odd prime. ∎

Next, we will investigate prism graphs. We define prism graphs as two cycles
each with $n$ vertices, the outside cycle with vertices $v_{1}$ to $v_{n}$ and
the inside cycle with vertices $u_{1}$ to $u_{n}$. The edges are defined as
$u_{i}u_{i+1}$, $v_{i}v_{i+1}$ for $i=1$ to $n-1$, $u_{n}u_{1}$, $v_{n}v_{1}$,
and $u_{i}v_{i}$ for $i=1$ to $n$. Prism graphs are also a type of generalized
Peterson graph, so we use the notation $GP(n,1)$. See Figure 5 for an example
of an odd prime labeling of a prism graph. Although we will show all prism
graphs have odd prime labelings, this is not the case for prime labelings.
When $n$ is odd, the prism graph is not prime and has only been shown to be
prime in certain cases for even $n$, as seen in [10].

Figure 5: An odd prime labeling of the prism graph GP(7,1)

######  Theorem 8.

The prism graph $GP(n,1)$ is odd prime for all $n\geq 3$.

###### Proof.

We begin by assigning the labels as follows: $\ell(u_{i})=4i-3$ and
$\ell(v_{i})=4i-1$ for $i=1$ to $n$. For all edges of the form $u_{i}v_{i}$,
we have $\gcd(\ell(u_{i}),\ell(v_{i}))=1$ because the labels are consecutive
odd integers. Likewise, the labels on the endpoints of the edges
$v_{i}v_{i+1}$ and $u_{i}u_{i+1}$, for $i=1$ to $n-1$, will be relatively
prime because they differ by $4$.

The last edges to consider are $u_{n}u_{1}$ and $v_{n}v_{1}$. Since
$\ell(u_{1})=1$, it will always be relatively prime with $\ell(u_{n})$. If
$n\not\equiv 1\pmod{3}$, then $\ell(v_{n})=4n-1$ is not a multiple of $3$ and
thus $\gcd(\ell(v_{n}),\ell(v_{1}))=\gcd(4n-1,3)=1$. This proves that $\ell$
is an odd prime labeling in this case. If $n\equiv 1\pmod{3}$ then 3 divides
$\ell(v_{n})=4n-1$, so a swap must be made in our labeling. We reassign
$\ell(u_{1})=3$ and $\ell(v_{1})=1$. Now we have
$\gcd(\ell(v_{n}),\ell(v_{1}))=1$ since $\ell(v_{1})=1$, and
$\gcd(\ell(u_{n}),\ell(u_{1}))=\gcd(4n-3,3)=1$ since $3$ does not divide
$4n-3$ when $n\equiv 1\pmod{3}$. Note that we still have
$\gcd(\ell(u_{1}),\ell(u_{2}))=\gcd(3,5)=1$ and
$\gcd(\ell(v_{1}),\ell(v_{2}))=\gcd(1,7)=1$. Therefore, we have created an odd
prime labeling in this case of $n\equiv 1\pmod{3}$, which proves that all
prisms are odd prime.

∎

Prisms are a special case with $k=1$ of the generalized Petersen graph,
$GP(n,k)$, where $n\geq 3$ and $1\leq k\leq\lfloor(n-1)/2\rfloor$. This graph
has $2n$ vertices $v_{1},v_{2},\ldots,v_{n},u_{1},u_{2},\ldots,u_{n}$ and $3n$
edges of the forms $v_{i}v_{i+1}$, $u_{i}u_{i+k}$, and $v_{i}u_{i}$ with
indices calculated modulo $n$. It has been shown in [13] that $GP(n,2)$ is odd
prime for any $n$ and conjectured in the same paper $GP(n,k)$ is odd prime for
any valid $n$ and $k$. While $GP(n,k)$ is not prime for any odd $k$, Theorem 5
add evidence to their odd prime conjecture, although it remains open for
$k>2$.

We next turn our focus onto stacked prism graphs, denoted by $Y_{k,n}$ with
$k\geq 3$ and $n\geq 1$, which is a generalization of prisms graphs. They
consist of $n$ polygons each with $k$ vertices that are connected by edges
between consecutive polygons. More formally, $Y_{k,n}$ is the Cartesian
product of a cycle of length $k$ with a path of length $n$, or $C_{k}\square
P_{n}$. We will show triangular, pentagonal, and hexagonal stacked prisms have
odd prime labelings. Additionally, we will extend these results for stacked
prisms with $2^{m}$ sides on the polygons. With respect to prime labelings,
$Y_{k,n}$ is not prime for any odd $k$. No work on the even $k$ case has been
previously published, although the independence number of $Y_{k,n}$ for even
$k$ would lead one to believe they are prime.

First, we will consider triangular stacked prisms, $Y_{3,n}$. We use $v_{i,j}$
with $1\leq j\leq 3$ to refer to the vertices on the $i$th triangle. The edges
are defined as $v_{i,1}v_{i,2}$, $v_{i,2}v_{i,3}$, and $v_{i,3}v_{i,1}$ for
$i=1,2,\ldots,n$ and $v_{i,j}v_{i+1,j}$ with $1\leq i\leq n-1$ and $1\leq
j\leq 3$. Figure 6 shows an example of an odd prime labeling on a triangular
stacked prism with $n=4$.

Figure 6: An odd prime labeling of a triangular stacked prism $Y_{3,4}$

######  Theorem 9.

The triangular stacked prism, $Y_{3,n}$, is odd prime for all $n\geq 1$.

###### Proof.

We will refer to the table below to label this graph. For any $v_{i,j}$ with
$i\leq 3$, let $\ell(v_{i,j})$ be the corresponding value in the table. For
any $v_{i,j}$ with $i>3$, this means that $i=3a+b$ for some positive integer
$a$ and some integer $b$ with $0\leq b\leq 2$. Then we assign
$\ell(v_{i,j})=\ell(v_{b,j})+18a$.

|  $v_{i,1}$ |  $v_{i,2}$ |  $v_{i,3}$
---|---|---|---
$i=1$ |  1 |  3 |  5
$i=2$ |  9 |  11 |  7
$i=3$ |  17 |  13 |  15

By inspecting the table above, for $i=1$ to $3$, we can see that the
difference between the labels of the adjacent vertices $v_{i,j}$ and
$v_{i+1,j}$ is always $2$ or $8$. Similarly, the difference between the labels
of adjacent vertices $v_{i,j}$ and $v_{i,k}$ within the same triangle will be
$2$ or $4$. Considering one more level in the stacked prism, when $i=4$, the
labels of this triangle are shifted by 18 from the first triangle to be
$\ell(v_{4,1})=19$, $\ell(v_{4,2})=21$, and $\ell(v_{4,3})=23$. This implies
the difference between labels of the vertices $v_{3,j}$ and $v_{4,j}$ are
either $2$ or $8$.

Note that for $i>4$ the adjacent labels will remain relatively prime because
adding the same multiples of $18$ will preserve the differences in the labels
that were all powers of $2$. Thus all triangular stacked prism graphs have an
odd prime labeling.

∎

Pentagonal stacked prisms, $Y_{5,n}$, are very similar to triangular stacked
prisms as the name suggests, but with pentagons in each layer of the prism. We
refer to the vertices on the $i$th pentagon as $v_{i,j}$ with $1\leq j\leq 5$.
The edges are defined for each $i=1,2,\ldots,n$ as $v_{i,j}v_{i,j+1}$ with
$1\leq j\leq 4$ and $v_{i,5},v_{i,1}$, and for $i=1,2,\ldots,n-1$ as
$v_{i,j},v_{i+1,j}$ with $1\leq j\leq 5$ . An example of a pentagonal stacked
prism with an odd prime labeling is displayed in Figure 7.

Figure 7: An odd prime labeling of a pentagonal stacked prism graph $Y_{5,6}$

######  Theorem 10.

The pentagonal stacked prism, $Y_{5,n}$ is odd prime for all $n\geq 1$.

###### Proof.

As in the last proof, we will provide a table of labels for the first several
layers of the stacked prism. For any $v_{i,j}$ with $i\leq 5$, we assign
$\ell(v_{i,j})$ to be the value in the table below. For any $v_{i,j}$ with
$i>5$ we have $i=5a+b$ for some positive integer $a$ and integer $b$ with
$0\leq b\leq 4$. Then assign $\ell(v_{i,j})=\ell(v_{b,j})+50a$.

|  $v_{i,1}$ |  $v_{i,2}$ |  $v_{i,3}$ |  $v_{i,4}$ |  $v_{i,5}$
---|---|---|---|---|---
$i=1$ |  1 |  3 |  7 |  9 |  5
$i=2$ |  17 |  19 |  15 |  11 |  13
$i=3$ |  25 |  21 |  23 |  27 |  29
$i=4$ |  33 |  37 |  39 |  35 |  31
$i=5$ |  49 |  45 |  41 |  43 |  47

By inspection of the table, it is clear that the difference between the labels
of adjacent vertices $v_{i,j}$ and $v_{i+1,j}$ is either $2$, $8$ or $16$. We
can also see that the difference between labels of adjacent vertices $v_{i,j}$
and $v_{i,j+1}$ for $1\leq j\leq 4$ and $v_{i,5}$ and $v_{i,1}$ will always be
$2$ or $4$. Adjacent vertices from the fifth pentagon and the sixth one after
shifting the labels by 50 to get $\ell(v_{6,j})=\ell(v_{1,j})$ also have
labels that differ by $2$, $8$, or $16$.

For $i>5$, shifting by the same multiple of $50$ will preserve the differences
in adjacent labels to keep them as powers of $2$. Thus all pentagonal stacked
prisms have an odd prime labeling.

∎

We continue with another type of stacked prism graph, $Y_{6,n}$, the hexagonal
stacked prism graph. The vertices on the $i$th hexagon are referred to as
$v_{i,j}$ with $1\leq j\leq 6$. The edges are defined for $i=1,2,\ldots,n$ as
$v_{i,j},v_{i,j+1}$ with $1\leq j\leq 5$ and $v_{i,6},v_{i,1}$, and for
$i=1,2,\ldots,n-1$ as $v_{i,j},v_{i+1,j}$ with $1\leq j\leq 6$. Figure 8
includes an example of a hexagonal stacked prism with an odd prime labeling.

Figure 8: An odd prime labeling of a hexagonal stacked prism $Y_{6,4}$

######  Theorem 11.

The hexagonal stacked prism, $Y_{6,n}$, is odd prime for all $n\geq 1$.

###### Proof.

As in previous stacked prism results, for $v_{i,j}$ with $i\leq 3$, we assign
$\ell(v_{i,j})$ as the value in the table below. For $i>3$, we have $i=3a+b$
for some positive integer $a$ and an integer $b$ with $0\leq b\leq 2$. In this
case, we assign $\ell(v_{i,j})=\ell(v_{b,j})+36a$.

|  $v_{i,1}$ |  $v_{i,2}$ |  $v_{i,3}$ |  $v_{i,4}$ |  $v_{i,5}$ |  $v_{i,6}$
---|---|---|---|---|---|---
$i=1$ |  1 |  9 |  11 |  3 |  7 |  5
$i=2$ |  17 |  13 |  15 |  19 |  23 |  21
$i=3$ |  33 |  29 |  31 |  35 |  27 |  25

One can see from the table that the difference between the labels of adjacent
vertices $v_{i,j}$ and $v_{i+1,j}$ is $4$ or $16$. Meanwhile, the difference
between labels of adjacent vertices $v_{i,j}$ and $v_{i,j+1}$ for $1\leq j\leq
5$ and $v_{i,6}$ and $v_{i,1}$ will always be $2,4$ or $8$. When considering
the edges between the third and fourth hexagons, the labels after shifting by
$36$ on the fourth hexagon are $37$, $45$, $47$, $39$, $43$, and $41$,
creating differences of $4$ and $16$.

For $i>3$ adjacent labels will continue to be relatively prime because adding
the same multiples of $36$ will preserve the differences from the earlier
cases of $i$. Thus all hexagonal stacked prisms have an odd prime labeling.

∎

We now expand our results on stacked prisms to polygons where the number of
sides are any power of $2$. As with our previous cases, we refer to the
vertices on the $i$th polygon as $v_{i,j}$ where $1\leq j\leq 2^{m}$. The
edges are the following: $v_{i,j},v_{i,j+1}$ with $1\leq j\leq 2^{m}-1$ and
$v_{i,1},v_{i,j}$ for $1\leq i\leq n$, and $v_{i,j},v_{i+1,j}$ for $1\leq
j\leq 2^{m}$ and $1\leq i\leq n-1$.

######  Theorem 12.

The $2^{m}$-sided polygonal stacked prism, $Y_{2^{m},n}$, is odd prime for all
$m\geq 2$ and $n\geq 1$.

###### Proof.

We label the vertices on the $i$th polygon with the values from
$(i-1)2^{m+1}+1$ to $i\cdot 2^{m+1}-1$ in this order:

$v_{i,1},v_{i,2^{m}},v_{i,2},v_{i,2^{m}-1},v_{i,3},\ldots,v_{i,2^{m-1}+2},v_{i,2^{m-1}},v_{i,2^{m-1}+1}.$

Using this alternating pattern will ensure that all adjacent labels on each
polygon will be separated by a power of $2$, particularly $2$ or $4$. The
difference between the labels $\ell(v_{i,1})$ and $\ell(v_{i+1,1})$ is

$i\cdot 2^{m+1}+1-((i-1)2^{m+1}+1)=2^{m+1}.$

Likewise, all other edges of the form $v_{i,j}v_{i+1,j}$ have labels differing
$2^{m+1}$ as well. Hence all adjacent labels are relatively prime by
Observation 3 (i), making all $2^{m}$-sided polygonal stacked prisms odd
prime. ∎

As one considers generalizing our previous results on stacked prisms to
attempt to create an odd prime labeling of $Y_{k,n}$ for any $k\geq 3$, it is
worth noting that the independence number of this graph is
$\lfloor\frac{k}{2}\rfloor\cdot n$. This is well above the required
independence number from Lemma 2 of $\lfloor\frac{kn+1}{3}\rfloor$ to make an
odd prime labeling possible.

We believe our approach would work for any $k$ to find a permutation of the
labels $1,3,\ldots,2k-1$ for the first $k$-polygon, followed by a mapping to
match these to the labels $2k+1,2k+3,\ldots,4k-1$ with each difference being a
power of 2. The mapping could then be repeated for each subsequent
$k$-polygon. However, constructing this mapping for a general $k$ has eluded
us, leaving the following as a conjecture.

######  Conjecture 13.

The $k$-polygonal stacked prism, $Y_{k,n}$, is odd prime for all $k\geq 3$ and
$n\geq 1$.

One well-studied class of graphs within the field of prime labeling is the set
of grid graphs, $P_{m}\times P_{n}$. It is conjectured that $P_{m}\times
P_{n}$ is prime for all $m,n\geq 2$, and many partial results have been proven
for certain cases of $m$ and $n$ [12, 18], and in particular ladder graphs,
$P_{m}\times P_{2}$, have been proven to be prime for any length $m$ [5].
Ladder graphs were shown in [21] to be odd prime, but grid graphs with higher
values of $m$ have yet to be investigated for odd prime labelings.

Our results on stacked prisms easily translate into odd prime labelings of
grid graphs since $P_{m}\times P_{n}$ is the graph $Y_{m,n}$ with the edges
between vertices $v_{i,n}$ and $v_{i,1}$ removed. Therefore, Lemma 1 directly
proves the following.

######  Corollary 14.

Grid graphs $P_{m}\times P_{n}$ are odd prime for $m=3,5,6,$ and $2^{k}$ with
$k\geq 2$ and for any $n$.

##  4 Trees

Various classes of trees have been shown to have prime labelings, providing
evidence for the conjecture by Entringer that all trees are prime. With
regards to odd prime labelings, only paths [13], unions of paths, and star
graphs (or $K_{1,n}$) [21] have been shown to be odd prime. We will construct
odd prime labelings for several other classes of trees to support the
following conjecture.

######  Conjecture 15.

All trees are odd prime.

We begin with two types of trees that were shown in [8] to have prime
labelings. Spiders are a class of trees in which only one vertex has degree 3
or more. It can also be viewed as a collection of paths
$P_{n_{1}},P_{n_{2}},\ldots,P_{n_{k}}$ with one end of each path adjoined to a
central vertex. Figure 9 shows an example of spider with an odd prime
labeling.

Figure 9: An odd prime labeling of a spider graph

######  Theorem 16.

All spider graphs are odd prime.

###### Proof.

Begin by assigning the label 1 to the central vertex, which we will call $v$.
Then label the vertices of $P_{n_{1}}$ with $3,5,\ldots,2(n_{1}+1)-1$ in order
from the vertex adjacent to the $v$ outward to the leaf. Continue labeling the
other paths $P_{n_{2}},P_{n_{3}},\ldots,P_{n_{k}}$ similarly with the lowest
available label assigned to the vertex adjacent to $v$. This labeling is odd
prime since every pair of adjacent vertices within a path $P_{n_{i}}$ contains
consecutive odd labels, and any adjacent pair that includes $v$ involves the
label $1$. ∎

Next we consider perfect binary trees, which are rooted trees in which all
interior vertices have two children and all leaves are on the same level. Note
that these trees have been proven to be prime in [8], but were referred to as
a complete binary tree. See Figure 10 for an example of a perfect binary tree
with an odd prime labeling.

Figure 10: An odd prime labeling of a perfect binary tree with four levels

######  Theorem 17.

All perfect binary trees are odd prime.

###### Proof.

Assume $n$ is the number of levels of the binary tree, and consider the
vertices of level $i$ to be $v_{i,j}$, where $i=1,2,\ldots,n$ and
$j=1,2,\ldots,2^{i-1}$. We start with the following labels: $\ell(v_{1,1})=1$,
$\ell(v_{2,1})=3$, and $\ell(v_{2,2})=5$. Clearly the adjacent labels for the
first two levels are relatively prime. We will proceed by induction on $n$.
Assume that the first levels $1$ to $k$ are labeled such that all adjacent
pairs are assigned relatively prime labels and with level $k$ containing the
labels $\\{2^{k}-1$, $2^{k}+1$, …, $2^{k+1}-3\\}$. Note that our chosen labels
for levels $1$ and $2$ also meet this second condition, so they can be viewed
as our base case.

We now label level $k+1$. For each $v_{k,j}$ with $\ell(v_{k,j})=x$, we label
its children $x+2^{k}$ and $x+2^{k+1}$. Adding $2^{k}$ to the labels of row
$k$ results in the labels $\\{2^{k+1}-1,2^{k+1}+1,\ldots,2^{k+1}+2^{k}-3\\}$.
Similarly, adding $2^{k+1}$ generates labels
$\\{2^{k+1}+2^{k}-1,2^{k+1}+2^{k}+1,\ldots,2^{k+2}-3\\}$. These $2$ sets of
labels are disjoint and when combined form the set
$\\{2^{k+1}-1,2^{k+1}+1,\ldots,2^{k+2}-3\\}$. The labels on $v_{i,j}$ and each
child are relatively prime because they differ by $2^{k}$ or $2^{k+1}$. Thus,
by induction, the labeling $\ell$ is an odd prime labeling for any number of
rows $n$.

∎

We next explore caterpillars, which are defined as a tree with a central path
of $n$ vertices called the spine, and all other vertices are distance $1$ from
the $n-2$ interior vertices of the spine. Two particular classes of
caterpillars were examined in the initial prime labeling paper by Tout et al
[19], the first of which being caterpillars with the highest degree vertex
being bounded above by $5$. Figure 11 includes such a caterpillar with an odd
prime labeling, and the following result describes a method of labeling these
caterpillars with small degree vertices.

Figure 11: An odd prime labeling of a caterpillar with vertices having at most
degree 5

######  Theorem 18.

All caterpillars with maximum degree at most $5$ are odd prime.

###### Proof.

Assume the caterpillar has $n$ vertices on its spine, and let those vertices
be $v_{1}$, $v_{2}$,…,$v_{n}$. Begin by labeling $v_{1}$ as $\ell(v_{1})=1$,
so $\gcd(\ell(v_{1}),\ell(v_{2}))=1$ regardless of what the label of $v_{2}$
is. We will sequentially label each $v_{i}$ from $i=2$ to $n-1$ along with its
adjacent leaves, where we consider $m$ to be the lowest unused odd integer
thus far.

  * –

If $\deg(v_{i})=2$, assign $\ell(v_{i})=m$.

  * –

If $\deg(v_{i})=3$, then at least one of $m$ or $m+2$ is not a multiple of
$3$. Assign the smallest such value as $\ell(v_{i})$ and the other label to
its leaf.

  * –

If $\deg(v_{i})=4$, then one of $m$, $m+2$, and $m+4$ is a multiple of $3$,
and at most one is a multiple of $5$. Therefore, at least one of $m$, $m+2$,
and $m+4$ is neither a multiple of $3$ or $5$. Assign the smallest such value
as $\ell(v_{i})$ and the other two labels to its leaves.

  * –

If $\deg(v_{i})=5$, at most two of $m$, $m+2$, $m+4$, and $m+6$ are a multiple
of $3$, and at most one is a multiple of $5$. Hence at least one of these is
not a multiple of $3$ or $5$. Assign the smallest such integer as
$\ell(v_{i})$, and the remaining labels to its three leaves.

Finally we assign $\ell(v_{n})$ to be the next available odd integer. For each
edge $v_{i}u$ where $u$ is a leaf, $\gcd(\ell(v_{i}),\ell(u))=1$ since their
difference is $2$ or $4$ with one possible exception. In the case of
$\deg(v_{i})=5$, we may have that the adjacent labels are $m$ and $m+6$. Since
the label of $v_{i}$ is selected to not be a multiple of $3$, then we know
$\gcd(m,m+6)=1$ as well.

For edges of the form $v_{i}v_{i+1}$ with $i=2,3,\ldots,n-2$, we consider each
possible common prime factor. The only case when $3$ divides $\ell(v_{i})$ is
if $\deg(v_{i})=2$, since we avoided multiples of $3$ on the spine with higher
degree vertices. Then $3$ can only be a common factor of $\ell(v_{i})$ and
$\ell(v_{i+1})$ if $\deg(v_{i})=\deg(v_{i+1})=2$, but in that case
$\ell(v_{i})$ and $\ell(v_{i+1})$ would be consecutive odd integers and hence
won’t have a common factor of $3$.

A common factor of $5$ would require $\deg(v_{i})$ and $\deg(v_{i+1})$ to be
at most $3$ since multiples of $5$ were avoided for vertices with degree $4$
or $5$. This implies the greatest difference between $\ell(v_{i})$ and
$\ell(v_{i+1})$ could be $6$, but a difference of at least $10$ would be
necessary to share a common factor of $5$.

In order to have a common factor of $7$, we would need
$\ell(v_{i+1})-\ell(v_{i})=14$. This can only occur if
$\deg(v_{i})=\deg(v_{i+1})=5$ with $\ell(v_{i})=m$ and $\ell(v_{i+1})=m+14$,
where the leaves of $v_{i+1}$ would be labeled as $m+8$, $m+10$, and $m+12$.
However, at least one of those $3$ labels is not a multiple of $3$ or $5$, and
being less than $m+14$, it would have been assigned as $\ell(v_{i+1})$. This
precludes $\ell(v_{i})$ and $\ell(v_{i+1})$ from having a common factor of
$7$.

Since our labeling is created with the largest difference possible in the
labels for $v_{i}$ and $v_{i+1}$ being $14$, their labels cannot share a prime
factor larger than $7$. Thus, $\gcd(\ell(v_{i}),\ell(v_{i+1}))=1$. for
$i=2,3,\ldots,n-2$.

Lastly, we must justify why $v_{n-1}$ and $v_{n}$ are labelled by relatively
prime integers. The construction of our labeling implies that the only way a
multiple of $3$ would be a label on the spine is if the degree of $v_{n-1}$
was $2$, but then $\ell(v_{n})$ would be the next consecutive odd integer and
thus $\gcd(\ell(v_{n-1}),\ell(v_{n}))=1$. If $\deg(v_{n-1})>2$, a non-multiple
of $3$ would have been chosen as its label. Then if the $\ell(v_{n})$ is a
multiple of $3$, we know $\ell(v_{n-1})$ would not be a multiple of $3$. For
common prime factors of 5 or higher, we note that since $\deg(v_{n-1})\leq 5$,
the largest difference between the labels of $v_{n-1}$ and $v_{n}$ is 8. Thus
no common factors of 5 or higher can exist, implying
$\gcd(\ell(v_{n-1}),\ell(v_{n}))=1$.

Therefore, all adjacent vertices have relatively prime labels, so there exists
an odd prime labeling for all caterpillars with maximum degree at most 5. ∎

We next examine a second set of caterpillars in which the interior vertices of
the tree have the same degree. Referring to the leaves of these caterpillars
as toes, we refer to a $t$-toed caterpillar as one where each interior vertex
has degree $t+2$. Two examples of $t$-toed caterpillars can be seen in Figure
12 complete with an odd prime labelings.

Figure 12: Odd prime labelings of two $t$-toed caterpillars, one of length
$10$ and $t=1$ where a reordering of the spine labels is needed, and one with
length $7$ and $t=3$.

This particular caterpillar was also shown in [19] to have a prime labeling
for any length and any number of toes, where a coprime matching theorem
developed in [15] was utilized to pair labels on the spine to the ones on the
toes. We use a similar approach relying on a result by Robertson and Small,
particularly Theorem 3 in [16]. They proved that given integers $a$ and $b$
which share no odd prime divisors less than $2n-1$, there exists a mapping $h$
from the set of the first $n$ odd integers, $O=\\{1+2r\;|\;0\leq r\leq
n-1\\}$, to the set $S=\\{a+rb\;|\;0\leq r\leq n-1\\}$ in which
$\gcd(m,h(m))=1$ for all $m\in O$. We will also rely on the following
reordering lemma to aid in this proof.

######  Lemma 19.

Given a sequence of $n+1$ consecutive odd integers
$\\{x_{i}\\}_{i=1}^{n}=\\{m,m+2,\ldots,m+2n\\}$ and a specified entry $x_{j}$,
there exists a reordering into the sequence
$\\{x_{i_{1}},x_{i_{2}},\ldots,x_{i_{n}},x_{j}\\}$ such that each successive
difference is a power of $2$. That is, for each $k=2,3,\ldots,n$,
$|x_{i_{k}}-x_{i_{k-1}}|=2^{s}$ and $|x_{j}-x_{i_{n}}|=2^{t}$ for some
integers $s,t\geq 1$.

###### Proof.

If $j=n$, then the original sequence does not need to be reordered since every
difference is $2$ initially. For $j<n$, we consider the binary expansion of
the difference of the last term and our specified entry:
$m+2n-x_{j}=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{b}}$. We can assume
$a_{1}>a_{2}>\cdots>a_{b}\geq 1$ where the last inequality is true since
$m+2n$ and $x_{j}$ are both odd.

We first alter the sequence by removing the entries
$x_{j},x_{j}+2^{a_{1}},x_{j}+2^{a_{1}}+2^{a_{2}},\ldots,x_{j}+2^{a_{1}}+\cdots+2^{a_{b-1}}$
and will refer to the remaining entries as
$x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}},m+2n$. Observe that since the exponents
in the binary expansion were each greater than 1, no pair of consecutive
entries were removed from the sequence. Therefore, the successive differences
of the shortened sequence are either 2 or 4.

We now append our removed entries at the end, but in reverse order, to create
the following sequence:

$x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}},m+2n,x_{j}+2^{a_{1}}+\cdots+2^{a_{b-1}},\ldots,x_{j}+2^{a_{1}}+2^{a_{2}},x_{j}+2^{a_{1}},x_{j}.$

The pair $m+2n$ and $x_{j}+2^{a_{1}}+\cdots+2^{a_{b-1}}$ has a difference of
$2^{a_{b}}$, and the subsequent pairs differ by each successive power of $2$
from the binary expansion. Thus, we have reordered the sequence with $x_{j}$
as the last term with every successive pair differing by a power of $2$. ∎

######  Theorem 20.

All $t$-toed caterpillars are odd prime for any length and any number of toes
$t$.

###### Proof.

Consider a caterpillar with length $n+2$ in which the $n$ interior vertices
are of degree $t+2$. Then there are $n(t+1)+2$ vertices, giving us a labeling
set of $\\{1,3,\ldots,2n(t+1)+1,2n(t+1)+3\\}$. We refer to the vertices on the
spine as $u,v_{1},v_{2},\cdots,v_{n},w$ and the toes from interior vertex
$v_{i}$ as $x_{i,1},x_{i,2},\ldots,x_{i,t}$.

We begin our labeling $\ell$ by assigning $\ell(v_{i})=2i-1$ for each
$i=1,2,\ldots,n$. Our two largest labels, $2n(t+1)+1$ and $2n(t+1)+3$, will be
used to label the ends of the spine, vertices $u$ and $w$. However, it is
possible that both of these labels share a common factor with
$\ell(v_{n})=2n-1$. Additionally, if $t$ is sufficiently large compared to
$n$, one of the two labels may share a common factor with each label from $3$
to $2n-1$. Even in this most extreme case, the other of $2n(t+1)+1$ or
$2n(t+1)+3$ must be relatively prime with $3$ since these two largest labels
differ by 2. Hence, we can conclude that one of $2n(t+1)+1$ and $2n(t+1)+3$
will be relatively prime with at least one of the interior labels
$3,5,\ldots,2n-1$, say the label $2k-1$ for some $2\leq k\leq n$. Then we
relabel $\ell(v_{n})=2k-1$, assign as $\ell(w)$ whichever of $2n(t+1)+1$ and
$2n(t+1)+3$ is relatively prime with $2k-1$, and assign the other of those two
labels to $u$. By Lemma 19, we can reorder the labels $3,5,\ldots,2n-1$ on the
interior vertices to maintain $\ell(v_{1})=1$, make this reassignment of
$\ell(v_{n})=2k-1$, and have the labels of each pair of adjacent vertices
differ by a power of $2$. Note that the vertex $u$ is only adjacent to
$v_{1}$, which is labelled by $1$, so our current labeling of the spine has
relatively prime labels at each adjacent pair of vertices.

For each $j=1,2,\ldots,t$, we next assign the labels
$2nj+1,2nj+3,\ldots,2n(j+1)-1$ to the vertices
$x_{1,j},x_{2,j},\ldots,x_{n,j}$. By Theorem 3 in [16], there is a function
$h$ pairing the set of labels of the interior vertices $\\{1,3,\ldots 2n-1\\}$
with the set $\\{2nj+1,2nj+3,\ldots,2n(j+1)-1\\}$ such that $\gcd(m,h(m))=1$
for all $m\in\\{1,3,\ldots 2n-1\\}$. Notice that we are applying this theorem
with $a=2nj+1$ and $b=2$, so clearly the condition about odd prime divisors of
these two integers is met. Thus, for a vertex $v_{i}$ with $\ell(v_{i})=m$, we
assign $\ell(x_{i,j})=h(m)$, resulting in this interior vertex and its
adjacent leaf having relatively prime labels. Continuing this for each $j$ up
to the value $t$ will label all the toes of the caterpillar, ending with the
label $2n(t+1)-1$. Thus, we have used the labels
$1,3,\ldots,2n(t+1)-1,2n(t+1)+1,2n(t+1)+3$, and every pair of adjacent
vertices is labelled with relatively prime integers, proving our labeling is
odd prime. ∎

The last tree we will examine is a firecracker graph, denoted $F_{n,k}$. This
graph consists of a path with $n$ vertices, in which each vertex in the path
is joined by an edge with the center of a $(k-1)$-star. Firecrackers were
shown in [16] to be prime. See Figure 13 for an example of a firecracker graph
with an odd prime labeling.

Figure 13: An odd prime labeling of a firecracker graph $F_{5,4}$

######  Theorem 21.

The firecracker graph $F_{n,k}$ is odd prime for all $n>1$ and $k\geq 3$.

###### Proof.

Let $v_{1},v_{2},\ldots,v_{n}$ be the vertices on the path,
$u_{1},u_{2},\ldots,u_{n}$ be the centers of the adjoined stars, and
$w_{i,1},w_{i,2},\ldots,w_{i,k-2}$ be the leaves from each vertex $u_{i}$. We
start by labeling the path vertices $v_{1}$ to $v_{n}$ with the odd integers
from $2n+1$ to $4n-1$, respectively. We then apply the coprime matching
theorem used in Theorem 20 to create the bijection
$h:\\{1,3,\ldots,2n-1\\}\rightarrow\\{2n+1,2n+3,\ldots,4n-1\\}$. Now use the
inverse of $h$ to assign the label for the center of each star as
$\ell(u_{i})=h^{-1}(\ell(v_{i})).$ We next apply the same matching theorem to
create the labels for $w_{i,j}$ from $j=1,2,\ldots,k-2$ by using
$\ell(w_{i,j})=h_{j}(\ell(u_{i}))$ where the function $h_{j}$ is mapped from
$\\{1,3,\ldots,2n-1\\}$ to $\\{2(j+1)n+1,2(j+1)n+3,\ldots,2(j+2)n-1\\}$.

The adjacent pairs $v_{i}v_{i+1}$ have relatively prime labels since they are
labelled by consecutive odd integers. For the remaining adjacent vertices, we
have $\gcd(\ell(u_{i}),\ell(v_{i}))=1$ and $\gcd(\ell(u_{i}),\ell(w_{i,j}))=1$
because the inputs and outputs of $h$ and $h_{j}$ are relatively prime by
Theorem 3 in [16]. Thus, every firecracker $F_{n,k}$ has an odd prime
labeling. ∎

##  5 Powers of graphs

All of the graphs discussed thus far have been odd prime or at least
conjectured to be so. However, we conclude our investigation of specific
classes of graphs with a class involving powers of graphs that is not odd
prime for certain cases. In general we define the $k$th power of a graph $G$,
denoted by $G^{k}$, to have the same vertex set as $G$, but additional edges
are included between vertices $u,v\in V(G)$ for which $d(u,v)\leq k$. By
$d(u,v)$, we are referring to the distance between the two vertices, or
likewise the length of the shortest path from $u$ to $v$.

We particularly will examine powers of paths and cycles. Seoud and Youssef
[17] showed that $P_{n}^{k}$ and $C_{n}^{k}$ for $k\geq 2$ were not prime with
exception of a few small cases of $n$, such as when $n=3$ since these graphs
would just be $K_{3}$. We will show that $P_{n}^{2}$, the square of a path, is
odd prime for all $n$; however, the square of a cycle and higher powers of
these two graphs won’t always be odd prime. An odd prime labeling of
$P_{11}^{2}$ can be observed in Figure 14, where the path consists of the
diagonal edges while the connections between vertices of distance $2$ are
horizontal.

Figure 14: An odd prime labeling of $P_{11}^{2}$

######  Theorem 22.

The square of a path, $P_{n}^{2}$, is odd prime for any length $n$.

###### Proof.

Consider the vertices of the path $P_{n}$ as $v_{1},v_{2},\ldots,v_{n}$ with
the additional edges of the form $v_{i}v_{i+2}$ from $i=1$ to $n-2$ to form
$P_{n}^{2}$. We will label the vertices as $\ell(v_{i})=2i-1$ for all $1\leq
i\leq n$. Edges in $P_{n}$ clearly have relatively prime labels at the
endpoints since they are labeled with consecutive odd integers. Likewise, for
edges of the form $v_{i}v_{i+2}$, $\gcd(2i-1,2(i+2)-1)=\gcd(2i-1,2i+3)=1$
since the difference of the labels is 4. Thus, this is an odd prime labeling.
∎

We were able to successfully label $P_{n}^{2}$ with an odd prime labeling
because its independence number is
$\beta(P_{n}^{2})=\left\lceil\frac{n}{3}\right\rceil$, within the required
range given in Lemma 2 to be able to place the multiples of 3 on an
independent set of vertices. However, as discussed in [17] and [1], the cycle
squared has an independence number of
$\beta(C_{n}^{2})=\left\lfloor\frac{n}{3}\right\rfloor$, and for powers of
$k\geq 3$, the independence numbers generalize to be the following:

$\beta(P_{n}^{k})=\left\lceil\frac{n}{k+1}\right\rceil\text{ and
}\beta(C_{n}^{k})=\left\lfloor\frac{n}{k+1}\right\rfloor.$

This will ultimately limit our abilities to develop odd prime labelings of
certain cases of $C_{n}^{2}$. Nonetheless, specific cases such as $C_{7}^{2}$,
as seen in Figure 15, can be created, and on the higher powers of certain
paths and cycles as seen in the following results.

Figure 15: An odd prime labeling of the squared cycle $C_{7}^{2}$

######  Theorem 23.

The square of a cycle, $C_{n}^{2}$, is odd prime if and only if $n\not\equiv
2\pmod{3}$.

###### Proof.

For the case of $n\equiv 2\pmod{3}$, we have $n=3k+2$ for some
$k\in\mathbb{Z}$. Then the independence number of $C_{n}^{2}$ is

$\beta(C_{n}^{2})=\left\lfloor\frac{n}{3}\right\rfloor=\left\lfloor\frac{3k+2}{3}\right\rfloor=k.$

However, Lemma 2 requires $\beta(G)$ to be at least
$\lfloor\frac{n+1}{3}\rfloor=\lfloor\frac{3k+3}{3}\rfloor=k+1$, and hence
$C_{n}^{2}$ is not odd prime in this case.

For when $n\not\equiv 2\pmod{3}$, we label the vertices of the cycle
$v_{1},v_{2},\ldots,v_{n}$ as we did for $P_{n}^{2}$ in Theorem 22 with
$\ell(v_{i})=2i-1$. Since this was an odd prime labeling of the square of the
path, we only to check the additional edges $v_{n-1}v_{1}$, $v_{n}v_{1}$, and
$v_{n}v_{2}$. We have that $\gcd(2n-3,1)$, $\gcd(2n-1,1)$, and $\gcd(2n-1,3)$
are each 1, with the last one being due to our assumption of $n\not\equiv
2\pmod{3}$ forcing $2n-1$ to not be a multiple of 3. Thus, $C_{n}^{2}$ is odd
prime in these two cases of $n\equiv 0$ or $1\pmod{3}$. ∎

When examining higher powers of paths and cycles, the trivial labelings used
in the previous two theorems do not work. However, some small cases for $n$
will result in $P_{n}^{k}$ being odd prime once labels are reordered as long
as the independence number is large enough to create an odd prime labeling.
One such example is $P_{13}^{3}$ as shown in Figure 16. The following theorem
fully characterizes when $P_{n}^{k}$ and $C_{n}^{k}$ are odd prime for $k\geq
3$, where we note that only $n\geq k+2$ for paths are considered since the
graph would otherwise simply be the complete graph $K_{n}$.

Figure 16: An odd prime labeling of $P_{13}^{3}$

######  Theorem 24.

The following are true regarding the graphs $P_{n}^{k}$ and $C_{n}^{k}$

  * •

$P_{n}^{3}$ is odd prime if and only if $n=5,6,7,9,10,$ or $13$.

  * •

$P_{n}^{4}$ is odd prime if and only if $n=6$ or $7$.

  * •

$P_{n}^{5}$ is odd prime if and only if $n=7$.

  * •

$P_{n}^{k}$ with $k\geq 6$ is not odd prime for any $n\geq k+2$.

  * •

$C_{n}^{k}$ with $k\geq 3$ is not odd prime for any $n\geq k+2$.

###### Proof.

Since we have
$\displaystyle\beta(P_{n}^{k})=\left\lceil\frac{n}{k+1}\right\rceil$ as the
independence number of $P_{n}^{k}$, the inequality

$\beta(P_{n}^{3})=\left\lceil\frac{n}{4}\right\rceil<\left\lfloor\frac{n+1}{3}\right\rfloor$

can be verified for $n=8,11,12$, or when $n\geq 14$. Similarly,

$\beta(P_{n}^{4})=\left\lceil\frac{n}{4}\right\rceil<\left\lfloor\frac{n+1}{3}\right\rfloor$

for all $n\geq 8$ and

$\beta(P_{n}^{5})=\left\lceil\frac{n}{6}\right\rceil<\left\lfloor\frac{n+1}{3}\right\rfloor$

for all $n\geq 8$ are true as well. Finally, we have
$\displaystyle\beta(C_{n}^{k})=\left\lfloor\frac{n}{k+1}\right\rfloor<\left\lfloor\frac{n+1}{3}\right\rfloor$
for all $n\geq 5$ and $k\geq 3$. By Lemma 2, these inequalities justify each
of the non-odd prime cases in the statement.

For the cases where these graphs are odd prime, we use the following sequences
to label the vertices of the path:

  * •

$P_{5}^{3}$: $3,1,5,7,9$

  * •

$P_{6}^{3}$: $3,1,5,7,9,11$

  * •

$P_{7}^{3}$: $3,1,5,7,9,11,13$

  * •

$P_{9}^{3}$: $3,1,5,7,9,11,13,17,15$

  * •

$P_{10}^{3}$: $3,1,5,7,9,11,13,17,15,19$

  * •

$P_{13}^{3}$: $3,1,5,7,9,11,13,25,21,19,23,17,15$

  * •

$P_{6}^{4}$: $3,1,5,7,11,9$

  * •

$P_{7}^{4}$: $3,1,5,7,11,9,13$

  * •

$P_{7}^{5}$: $3,1,5,7,11,13,9$.

One can see that any labels that share factors of $3$, $5$, or $7$ are at
least distance $k+1$ apart on the path, making them odd prime labelings. ∎

##  6 Prime vs. Odd Prime Graphs

Results such as Theorems 4 (when considering odd-length cycles), 8 (also for
odd-length prisms), 9, 10, and 22 show that many classes of graphs are not
prime, but have an odd prime labeling. On the other hand, no examples of
graphs have been found to be prime, but not have an odd prime labeling. Our
expectation is that no such graphs exist, as summarized for the following
conjecture, first introduced as Conjecture 2.14 in [13] and Conjecture $1$ in
[21].

######  Conjecture 25.

Every prime graph is an odd prime.

One potential avenue to prove this conjecture involves the maximal prime
graph, $R_{n}$, defined in [17] as the graph consisting of vertices
$v_{1},v_{2},\ldots,v_{n}$ where $v_{i}v_{j}$ is an edge if and only if
$\gcd(i,j)=1$. Since all prime graphs of order $n$ are isomorphic to a
spanning subgraph of $R_{n}$, Conjecture 25 would be proven true if one could
develop an odd prime labeling of $R_{n}$ for any $n$. Namely, we need a
function $\ell:\\{v_{1},v_{2},\ldots,v_{n}\\}\rightarrow\\{1,3,\ldots,2n-1\\}$
for any $n\geq 1$ such that for all $i,j\in\\{1,2,\ldots,n\\}$, if
$\gcd(i,j)=1$, then $\gcd(\ell(v_{i}),\ell(v_{j}))=1$. This function could
then be used convert a prime labeling of any prime graph to an odd prime
labeling.

Figure 17: An odd prime labeling of $R_{12}$

We have been able to find general function for all $n$ still, but we conclude
this paper by showing the progress that has been made in developing one. In
order to maintain the relatively prime condition on adjacent labels, our
mapping is based on shifting each of the prime divisors of an input to the
next largest prime. As an example, for $v_{12}$ where $12=2\cdot 2\cdot 3$, we
assign $\ell(v_{20})=3\cdot 3\cdot 5=45$, provided that $n$ is largest enough
for $2n-1\geq 45$. When $n$ is not large enough for $45$ to be a usable label,
one of the available prime numbers between $n$ and $2n-1$ is usually assigned.
An example of one of these labeling functions being applied to the maximal
prime graph $R_{12}$ is shown in Figure 17.

######  Theorem 26.

All prime graphs of order $n\leq 50$ are odd prime.

###### Proof.

To prove this, we introduce a set of functions that would assign an odd prime
labeling to the vertices of the graph $R_{n}$ with $n\leq 50$. Given a
particular order $n$, Table 1 provides the sequence of labels used on the
vertices $v_{1},v_{2},\ldots,v_{n}$ of $R_{n}$. Use the row given by the set
in the first column which contains the given $n$, and then the first $n$
values in that row (or two rows) will be an odd prime labeling $\ell$ of
$R_{n}$. A Mathematica program has been used to verify the relatively prime
condition in which for each $i,j\in\\{1,2,\ldots,n\\}$ with $\gcd(i,j)=1$, we
have $\gcd(\ell(i),\ell(j))=1$ as well. ∎

$n$ | Sequence for $\ell(v_{1}),\ell(v_{2}),\ldots,\ell(v_{n})$ |
---|---|---
$[1,4]$ | 1 | 3 | 5 | 7 |  |
$[5,7]$ | 1 | 3 | 5 | 9 | 7 | 11 | 13 |  |
$[8,10]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 13 | 17 | 19 |  |
$[11,12]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 13 | 17 | 21 | 19 | 23 |  |
$[13,16]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 13 | 25 | 21 | 17 | 23 | 19 | 27 | 29 | 31 |  |
$\\{17\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 17 | 19 | 33 | 23 | 29 | 31 |  |
$[18,22]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 17 | 13 | 19 | 33 | 35 | 23 | 29 | 31 | 37 | 39 | 41 | 43 |  |
$[23,27]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 19 | 23 | 29 | 31 | 37 | 41 | 39 | 43 | 47 | 49
51 | 53 |  |
$\\{28\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 19 | 23 | 29 | 31 | 41 | 55 | 39 | 37 | 43 | 49
51 | 47 | 53 |  |
$[29,31]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 57 | 23 | 19 | 29 | 37 | 55 | 39 | 31 | 41 | 49
51 | 43 | 47 | 53 | 59 | 61 |  |
$[32,33]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 57 | 23 | 19 | 29 | 63 | 55 | 39 | 31 | 37 | 49
51 | 41 | 43 | 47 | 53 | 59 | 61 | 65 |  |
$\\{34\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 23 | 19 | 29 | 31 | 63 | 55 | 39 | 37 | 41 | 49
51 | 43 | 47 | 53 | 59 | 61 | 67 | 65 | 57 |  |
$[35,37]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 23 | 19 | 29 | 31 | 63 | 55 | 39 | 37 | 41 | 49
51 | 43 | 47 | 53 | 59 | 61 | 69 | 65 | 57 | 67 | 71 | 73 |  |
$\\{38\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 23 | 19 | 75 | 29 | 63 | 55 | 39 | 31 | 37 | 49
51 | 41 | 43 | 47 | 53 | 59 | 69 | 65 | 57 | 61 | 67 | 71 | 73 |  |
$[39,40]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 23 | 19 | 75 | 29 | 63 | 55 | 39 | 31 | 37 | 49
51 | 41 | 43 | 47 | 53 | 59 | 69 | 65 | 57 | 77 | 61 | 67 | 71 | 73 | 79 |  |
$[41,42]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 81 | 19 | 75 | 23 | 63 | 55 | 39 | 29 | 31 | 49
51 | 37 | 41 | 43 | 47 | 53 | 59 | 65 | 57 | 77 | 61 | 67 | 69 | 71 | 73 | 79 | 83 |  |
$\\{43\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 81 | 19 | 75 | 23 | 63 | 55 | 39 | 29 | 31 | 49
51 | 37 | 41 | 43 | 47 | 53 | 59 | 65 | 57 | 77 | 61 | 67 | 69 | 85 | 71 | 73 | 79 | 83 |  |
$[44,45]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 13 | 45 | 17 | 33 | 35 | 81 | 19 | 75 | 23 | 63 | 55 | 39 | 31 | 29 | 49
51 | 37 | 41 | 43 | 47 | 53 | 59 | 65 | 57 | 77 | 61 | 67 | 69 | 85 | 71 | 73 | 79 | 83 | 87 | 89 |  |
$\\{46\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 29 | 45 | 17 | 33 | 35 | 81 | 19 | 75 | 23 | 63 | 55 | 39 | 31 | 65 | 49
51 | 37 | 13 | 41 | 91 | 43 | 47 | 53 | 57 | 77 | 59 | 61 | 69 | 85 | 67 | 71 | 73 | 79 | 87 | 83 | 89 |  |
$\\{47\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 29 | 45 | 17 | 33 | 35 | 81 | 19 | 75 | 23 | 63 | 55 | 39 | 31 | 65 | 49
51 | 37 | 13 | 41 | 91 | 43 | 47 | 53 | 57 | 77 | 59 | 61 | 69 | 85 | 67 | 71 | 73 | 79 | 87 | 83 | 93 | 89 |  |
$[48,49]$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 29 | 45 | 17 | 33 | 35 | 81 | 59 | 75 | 23 | 63 | 55 | 39 | 31 | 65 | 49
51 | 37 | 13 | 41 | 91 | 43 | 47 | 19 | 53 | 77 | 57 | 61 | 69 | 85 | 67 | 71 | 73 | 79 | 87 | 83 | 93 | 89 | 95 | 97 |
$\\{50\\}$ | 1 | 3 | 5 | 9 | 7 | 15 | 11 | 27 | 25 | 21 | 29 | 45 | 17 | 33 | 35 | 81 | 59 | 75 | 23 | 63 | 55 | 39 | 31 | 65 | 49
51 | 37 | 99 | 41 | 91 | 43 | 47 | 19 | 53 | 77 | 57 | 61 | 69 | 85 | 67 | 71 | 73 | 79 | 87 | 83 | 93 | 89 | 95 | 97 | 13
Table 1: A table containing the sequence of labels used for an odd prime
labeling of $R_{n}$ for $n\leq 50$

## Acknowledgements

The authors are grateful for the support of the Austin Peay State University
Department of Mathematics and Statistics. They also thank the referees for
their comments and suggestions.

## References

  * [1] J. Asplund and N. B. Fox, Minimum coprime labelings for operations on graphs, Integers 19 (2019) Article A24.
  * [2] J. Asplund and N. B. Fox, Minimum coprime labelings of generalized Petersen and prism graphs, J. Integer Seq. 24 (2021) Article 21.3.5.
  * [3] A. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, and C. McBee, Coprime and prime labelings of graphs, J. Integer Seq. 19 (2016) Article 16.5.8.
  * [4] M. Cloys and N. B. Fox, Neighborhood-prime labelings of trees and other classes of graphs, Pi Mu Epsilon Journal 15 (2019) 9–21.
  * [5] N. Dean, Proof of the prime ladder conjecture, Integers 17 (2017) Article A40.
  * [6] T. Deretsky, S. M. Lee, and J. Mitchem, On vertex prime labelings of graphs, Graph Theory, Combinatorics, and Applications Vol. 1 (1991) 359–369.
  * [7] N. Diefenderfer, D. Ernst, M. Hastings, L. Heath, H. Prawzinky, B. Preston, J. Rushall, E. White, and A. Whittemore, Prime Vertex Labelings of Several Families of Graphs, Involve 9 (2016) No. 4, 667–688.
  * [8] H. L. Fu and K. C. Huang, On prime labellings, Discrete Math. 127 (1994) 181–186.
  * [9] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. DS6 (2014) .
  * [10] K. Haque, X. Lin, Y. Yang, and P. Zhao, On the prime labeling of generalized Petersen graph $P(n,1)$, Util. Math. 83 (2010) 95–106.
  * [11] C. Lee, Minimum coprime graph labelings, J. Integer Seq. 23 (2020) Article 20.11.4.
  * [12] T. Nicholas, S. Somasundaram, and V. Vilfred, Classes of prime labelled graphs, International Journal of Management and Systems 18 (2002) no. 2.
  * [13] U. M. Prajapati and K. P. Shah, On odd prime labeling, Int. J. Res. Anal. Rev. 5 (2018) 284–294.
  * [14] S. K. Patel and N. P. Shrimali, Neighborhood-prime labeling, Int. J. Math. Soft Comput. 6 (2015) 135–143.
  * [15] C. Pomerance and J. L. Selfridge, Proof of D. J. Newman’s coprime mapping conjecture, Mathematika 27 (1980) 69–83.
  * [16] L. Robertson and B. Small, On Newman’s conjecture and prime trees, Integers 9 (2009) 117–128.
  * [17] M. A. Seoud and M. Z. Youssef, On prime labelings of graphs, Congr. Numer. 141 (1999) 203–215.
  * [18] M. Sundaram, R. Ponraj, and S. Somasundaram, On a prime labeling conjecture, Ars Combin. 79 (2006) 205–209.
  * [19] A. Tout, A. N. Dabboucy, and K. Howalla, Prime labeling of graphs, Nat. Acad. Sci. Letters 11 (1982) 365–368.
  * [20] S. K. Vaidya and U. M. Prajapati, Some results on prime and $k$-prime labeling, J. Math. Research 3 (2011) 66–75.
  * [21] M. Z. Youssef and Z. S. Almoreed, On odd prime labeling of graphs, Open J. Discrete Appl. Math. 3 (2020) 33–40.