Minimum Coprime Labelings of Generalized Petersen and Prism Graphs

John Asplund Metron, Inc. Reston, VA 20190 USA

                  asplund@metsci.com

N. Bradley Fox Department of Mathematics and Statistics Austin Peay State University Clarksville, TN 37044 USA

                     foxb@apsu.edu

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.

1 Introduction

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 coprime labeling of G is a labeling of V using distinct labels from the set {1, …, m} for some integer m ≥ n in which adjacent vertices are labeled by relatively prime integers. If the integers 1, …, n are used as the labeling set, the labeling is called a prime labeling, and G is a prime graph or is simply referred to as 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 𝔭𝔯(G), is the minimum coprime number of G, and a coprime labeling with 𝔭𝔯(G) as the largest label is a minimum coprime labeling of G. A prime graph would have a minimum coprime number of 𝔭𝔯(G) = n.

Prime labelings of graphs were developed by Roger Entringer and first introduced by Tout, Dabboucy, and Howalla [14]. 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 [8]. Most of our upcoming results center around the concept of minimum coprime labelings, which were first studied by Berliner et al. [3] with their investigation of complete bipartite graphs of the form K_{n,n}. Asplund and Fox [1] 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 [11] 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}□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 3, 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 4 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 5 consists of results on minimum coprime number of stacked prism graphs, and finally we investigate a variation of a generalized Petersen graph in Section 6.

2 Preliminary material

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 independence number, denoted by α(G). Since even number labels must be assigned to independent vertices, the following criteria, first introduced by Fu and Huang [7], eliminates the possibility of a prime labeling on many classes of graphs.

Lemma 1. [7] If G is prime, then the independence number of G must satisfy α(G) ≥ ⌊\frac{|V (G)|}{2}⌋.

The generalized Petersen graph, denoted GP(n, k) where n ≥ 3 and 1 ≤ k ≤ ⌊(n − 1)/2⌋, consists of 2n vertices v_{1}, …, v_{n}, u_{1}, …, 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 α(GP(n, 1)) = n − 1 for odd n. Then by Lemma 1, 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 [12] 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 [2, 4, 6] 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. [9] 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 [12]. Dean [5] 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 [10], most work involving prime labelings of the generalized Petersen graph has been focused on the prism graph. Schluchter et al. [13] made a number theoretic conjecture to bolster the conjecture that GP(n, 1) is prime for all even n. Conjecture 2.1 [13] stated that for any even integer n, there exists an s ∈ [1, n − 1] such that n + s and 2n + s are prime. By verifying this conjecture for all even n up to 2.468 × 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.

Observation 2. For positive integers a, b, and k, the following hold:

• gcd(a, b) = gcd(ka, b).

• gcd(a, b) = gcd(a − b, b).

• gcd(a, b) = gcd(a + b, b).

• If a + b is prime, then gcd(a, b) = 1.

• If a − b is a prime p and both a and b are not multiples of p, then gcd(a, b) = 1.

3 Prism graphs

In this section, we provide several specific results for the minimum coprime number of GP(n, 1) and conjecture that 𝔭𝔯(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 1 for an example of our first result showing a minimum coprime labeling for the prism GP(11, 1).

Figure 1: Minimum coprime labeling for GP(11, 1)

Theorem 3. If n is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We construct a labeling ℓ in the following manner. We label v_{1}, …, v_{n} as 1, …, n and u_{1}, …, u_{n} with n + 1, …, 2n − 1, 2n + 1 respectively. All adjacent pairs in {v_{1}, …, v_{n}} and in {u_{1}, …, u_{n}} have consecutive labels except for v_{1}v_{n}, u_{n−1}u_{n}, and u_{1}u_{n}. The first pair includes 1 as one of the labels, and the second pair is labeled by consecutive odd labels. Lastly, ℓ(u_{1}) and ℓ(u_{n}) are relatively prime since gcd(n+1, 2n+1) = gcd(2n+2, 2n+1) = 1.

It remains to show that the labels ℓ(u_{i}) and ℓ(v_{i}) are relatively prime for each i. For i ≤ 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 2. Finally when i = n, we have gcd(2n + 1, n) = gcd(n + 1, n) = 1. Therefore, this is a coprime labeling, hence 𝔭𝔯(GP(n, 1)) ≤ 2n + 1. Since the independence number of GP(n, 1) is n−1 when n is odd, a prime labeling is not possible, making 𝔭𝔯(GP(n, 1)) > 2n. Thus when n is prime, we have 𝔭𝔯(GP(n, 1)) = 2n + 1.

Theorem 4. If n + 2 is prime, then 𝔭𝔯(GP (n, 1)) = 2n + 1.

Proof. We construct a labeling ℓ in the following manner. First we label v_{1}, …, v_{n} with the numbers 1, …, n, respectively, and then the vertices u_{1}, …, u_{n} with the labels n+3, …, 2n+ 1, n + 2, respectively.

Edges between vertices in {v_{1}, …, v_{n}} have vertices with consecutive labels or contain the label 1, and so gcd(ℓ(v_{i}), ℓ(v_{i+1})) = gcd(ℓ(v_{1}), ℓ(v_{n})) = 1. Edges between vertices in {u_{1}, …, 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}, …, u_{n}} are relatively prime. For i = 1, …, n − 1, since the difference of the labels on vertices u_{i} and v_{i} is n + 2, which is prime, gcd(ℓ(u_{i}), ℓ(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, 𝔭𝔯(GP(n, 1)) = 2n + 1 assuming n + 2 is prime.

Theorem 5. If 2n + 1 is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We construct a labeling ℓ in the following manner. First we label v_{1}, …, v_{n} as 1, …, n as in last theorem, but we label u_{1}, …, u_{n} in reverse order as 2n+1, 2n−1, 2n−2, …, n+1.

Edges connecting vertices in {v_{1}, …, v_{n}} have consecutive labels or contain the label 1, and so gcd(ℓ(v_{i}), ℓ(v_{i+1})) = gcd(ℓ(v_{1}), ℓ(v_{n})) = 1. Edges between vertices in {u_{1}, …, 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, …, n, since ℓ(u_{i}) + ℓ(v_{i}) = 2n + 1, we know that gcd(ℓ(u_{i}), ℓ(v_{i})) = 1 by Observation 2 because 2n + 1 is prime. Finally, the edge u_{1}v_{1} includes the label 1 on u_{1}. Thus, this is a coprime labeling that shows 𝔭𝔯(GP(n, 1)) = 2n + 1 when 2n + 1 is prime.

Theorem 6. If 2n − 1 is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. Notice that when n ≡ 2 (mod 3), then 2n − 1 is divisible by 3, so we may assume n ≢ 2 (mod 3). If n ≡ 0 (mod 3), we construct a labeling ℓ by first labeling v_{1}, …, v_{n} as 1, 2, …, n − 1, 2n − 1 and then label u_{1}, …, u_{n} as 2n − 2, 2n − 1, …, n, 2n + 1. One can see the pairs u_{i}u_{i+1} and v_{i}v_{i+1} have relatively prime labels, where gcd(ℓ(u_{1}), ℓ(u_{n})) = gcd(2n + 1, 2n − 2) = 1 since n is a multiple of 3 in this case. The pairs u_{i}v_{i} have relatively prime labels for i = 1, …, n − 1 since ℓ(u_{i}) + ℓ(v_{i}) = 2n + 1, which is assumed to be prime. Whereas for i = n, gcd(ℓ(u_{n}), ℓ(v_{n})) = 1 since these are consecutive odd integers.

If n ≡ 1 (mod 3), then use the same labeling as the previous case except ℓ(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 ≡ 1 (mod 3). In each case, the labeling is a minimum coprime labeling, proving 𝔭𝔯(GP(n, 1)) = 2n + 1 assuming 2n − 1 is prime.

For further results regarding minimum coprime labelings of prism graphs in other specific cases, see Appendix A. Using Theorems 3–6, along with Theorems 17–23 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.

Theorem 7. Let n ≥ 3 be odd. If there exists an s ∈ [3, n − 1] such that n + s + 1 and 2n + s + 2 are prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We use the labeling defined in Table 1 where the top row represents the vertices v_{1}, …, v_{n} and the bottom row represents the vertices u_{1}, …, u_{n}. The vertex pairs on edges of the form u_{1}v_{1}, u_{i}u_{i+1} and v_{i}v_{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_{i}v_{i} for i = 2, …, s have labels that add to n + s + 1, and the pairs u_{i}v_{i} for i = s + 1, …, 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 𝔭𝔯(GP(n, 1)) = 2n + 1 if such a value s exists.

\begin{matrix}1 & 2 & ⋯ & s − 1 & s & s + 1 & s + 2 & ⋯ & n − 1 & n \\ n + s + 1 & n + s − 1 & ⋯ & n + 2 & n + 1 & 2n + 1 & 2n & ⋯ & n + s + 3 & n + s + 2 \end{matrix}

Table 1: Labeling for Theorem 7

Recall that Conjecture 2.1 [13] states that for all even integers n, there is an s < n such that n + s and 2n + s are both prime. If this is true for all even integers, then the previous theorem would prove the subsequent conjecture for all odd n since applying Conjecture 2.1 to the even integer n + 1 would result in n + s + 1 and 2n + s + 2 being prime. Results by Schluchter et al. [13] combine with Theorem 7 to confirm the following conjecture for odd n < 2.468 × 10^{9}.

Conjecture 8. For all odd n ≥ 3, 𝔭𝔯(GP(n, 1)) = 2n + 1.

4 Generalized Petersen graphs with k = 2

We next consider the generalized Petersen graph in the case of k = 2. The vertices of GP(n, 2) with n ≥ 5 are still referred to as v_{1}, …, v_{n},u_{1}, …, u_{n} with the edges of the forms v_{i}v_{i+1}, u_{i}u_{i+2}, and v_{i}u_{i} in which indices calculated modulo n. An example of this type of graph with n = 5 is the well-known Petersen graph, which is shown with a minimum coprime labeling in Figure 2.

The independence number for generalized Petersen graphs when k = 2 is given by the formula ⌊\frac{4n}{5}⌋ through the study of minimum vertex covers of GP(n, 2) by Behsaz et al [2]. This results in the generalized Petersen graph with k = 2 not being prime for any value of n. The denominator of this formula for the independence number provides a natural direction by which to create an independent set for this graph by dividing GP(n, 2) into blocks that include 5 of the v_{i} and 5 of the u_{i} vertices. We utilize this technique in the following proof but limit ourselves for now to the case when n is a multiple of 5.

Figure 2: A minimum coprime labeling of the Petersen graph GP(5, 2)

Lemma 9. Let m be a positive integer. Then 𝔭𝔯(GP(5m, 2)) = 12m − 1.

Proof. We aim to construct a coprime labeling ℓ and later will show that it is minimal. We begin by assigning v_{1}, …, v_{5} the labels 2, 3, 5, 8, 9 and assigning u_{1}, …, u_{5} the labels 1, 4, 6, 7, 11, respectively. One can verify these ten labels form a coprime labeling when m = 1. For m > 1 we then define the following labeling for the block of ten vertices v_{5k+1}, …, v_{5k+5}, u_{5k+1}, …, u_{5k+5} for each 1 ≤ k < m:

\begin{matrix}ℓ(v_{5k+1}) = 12k + 2, & ℓ(v_{5k+4}) = 12k + 8, & ℓ(u_{5k+1}) = 12k + 1, & ℓ(u_{5k+4}) = 12k + 7, \\ ℓ(v_{5k+2}) = 12k + 3, & ℓ(v_{5k+5}) = 12k + 9, & ℓ(u_{5k+2}) = 12k + 4, & ℓ(u_{5k+5}) = 12k + 11. \\ ℓ(v_{5k+3}) = 12k + 5, & & ℓ(u_{5k+3}) = 12k + 10, \end{matrix} (1)

Figure 3: Visual representation of the labeling described in Equation (1)

As currently defined the labeling ℓ, which is displayed in Figure 3, is not enough to guarantee each pair of adjacent vertices has relatively prime labels, particularly for pairs of labels that have a difference of 5. We alter the labeling ℓ by addressing cases for specific k values based on the divisibility of 12k − 1, 12k − 3, and 12k + 5. Before altering ℓ, first note that no adjacent vertices are both labeled by even integers. One can also observe that no labels that are multiples of 3 are assigned to adjacent vertices, including the adjacent pairs whose labels differ by 9. Additionally, the final vertices in the last block u_{n−1}, u_{5m}, and v_{5m} are adjacent to the vertices u_{1}, u_{2}, and v_{1}, respectively. Since ℓ(u_{1}) = 1, it is relatively prime to the label of u_{n−1}. Likewise, ℓ(u_{2}) = 4 and ℓ(v_{1}) = 2, while ℓ(u_{5m}) = 12m − 1 and ℓ(v_{5m}) = 12m − 3 are both odd, making those adjacent pairs of labels also relatively prime.

As we define ℓ for the upcoming cases, the labels on vertices u_{5k+4}, u_{5k+5}, and v_{5k+5} are not changed except in Cases 4b, 4c, and 4d, and this occurs only as the subsequent block is labeled. These three vertices are the only ones within the block v_{5k+1}, …, v_{5k+5}, u_{5k+1}, …, u_{5k+5} that are adjacent to vertices in the subsequent block, hence leaving these three vertices unchanged is essential to guaranteeing that adjacent labels on vertices in different blocks are relatively prime. Let U_{k} = {u_{5k+1}, …, u_{5k+5}} and V_{k} = {v_{5k+1}, …, v_{5k+5}}.

Case 1: Suppose that 5 ∤ 12k − 1, 5 ∤ 12k − 3, and 5 ∤ 12k + 5.

Label the vertices U_{k} ∪ V_{k} as in Equation 1. As previously observed, pairs of adjacent vertices in U_{k} ∪ V_{k} or adjacent pairs between the vertices in U_{k} ∪ V_{k} and {v_{5k}, u_{5k}, u_{5k−1}} do not have labels that share a common factor of 2 or 3. The adjacent vertex pairs u_{5k}u_{5k+2}, v_{5k}v_{5k+1}, and v_{5k+3}u_{5k+3} have labels that differ by 5. Our assumptions for this case ensure that these pairs are not both divisible by 5, resulting in the relatively prime condition being satisfied.

Case 2: Suppose that 5 | 12k + 5.

Use the labeling ℓ from Equation (1) with the following redefined label:

ℓ(u_{5k+3}) = 12k + 6.  (2)

Since we assumed 5 | 12k + 5, it follows that 5 ∤ 12k − 1 and 5 ∤ 12k − 3, and thus after applying reasoning from Case 1, we need only check that ℓ(u_{5k+3}) is relatively prime with the labels of all neighbors of u_{5k+3}. Since u_{5k+3} is adjacent to u_{5k+1}, u_{5k+5} and v_{5k+3}, we need that gcd(12k + 1, 12k + 6) = 1, gcd(12k + 6, 12k + 11) = 1, and gcd(12k + 5, 12k + 6) = 1. The third equality is trivial, and the first two equalities follow immediately from the Case 2 assumption.

Case 3a: Suppose that 5 | 12k − 1 and 7 ∤ 12k − 3.

Use the labeling ℓ in Equation (1) with the following two redefined labels:

ℓ(u_{5k+2}) = 12k + 2, ℓ(v_{5k+1}) = 12k + 4.  (3)

Notice that since 5 divides 12k − 1, we have gcd(12k + 5, 12k + 10) = 1. As before, we need only to check that ℓ(u_{5k+2}) and ℓ(v_{5k+1}) are relatively prime with the labels of any adjacent vertices. Clearly, gcd(12k + 2, 12k + 3) = gcd(12k + 3, 12k + 4) = 1. Since both 12k + 2 and 12k +4 are not divisible by 3, we know that gcd(12k −1, 12k +2) = gcd(12k +1, 12k +4) = 1.

Since 7 is assumed to not divide 12k − 3, gcd(12k − 3, 12k + 4) = 1. Finally, our assumption of 5 | 12k − 1 implies 5 ∤ 12k + 2, hence gcd(12k + 2, 12k + 7) = 1.

Case 3b: Suppose that 5 | 12k − 1 and 7 | 12k − 3.

Use the labeling ℓ in Equation (1) with the following three redefined labels:

ℓ(u_{5k+2}) = 12k + 6, ℓ(v_{5k+2}) = 12k + 5, ℓ(v_{5k+3}) = 12k + 3.  (4)

We need only check that these new labels are relatively prime with labels of any neighboring vertices. It is clear that

gcd(12k + 6, 12k + 7) = gcd(12k + 5, 12k + 6) = gcd(12k + 3, 12k + 5) = 1.

Since 12k +2 is not divisible by 3, gcd(12k +2, 12k +5) = 1. By our assumption that 12k −1 is divisible by 5, gcd(12k + 3, 12k + 8) = 1. Since 12k − 3 is assumed to be divisible by 7, gcd(12k − 1, 12k + 6) = gcd(12k + 3, 12k + 10) = 1.

Case 4a: Suppose that 5 | 12k − 3 and 7 ∤ 12k − 3.

Use the labeling ℓ in Equation (1) with the following four redefined labels:

ℓ(v_{5k+1}) = 12k + 4, ℓ(v_{5k+4}) = 12k + 10, ℓ(u_{5k+2}) = 12k + 8, ℓ(u_{5k+3}) = 12k + 2. (5)

Clearly we have

gcd(12k+3, 12k+4) = gcd(12k+1, 12k+2) = gcd(12k+7, 12k+8) = gcd(12k+9, 12k+10) = 1.

Additionally, since none of the four reassigned labels are divisible by 3, it is clear that

gcd(12k + 1, 12k + 4) = gcd(12k + 2, 12k + 5) = gcd(12k + 7, 12k + 10)
= gcd(12k − 1, 12k + 8) = gcd(12k + 2, 12k + 11) = 1.

Our assumptions in this case include that 7 ∤ 12k − 3 and also imply that 5 ∤ 12k + 8 or 12k + 10. Thus we have

gcd(12k − 3, 12k + 4) = gcd(12k + 3, 12k + 8) = gcd(12k + 5, 12k + 10) = 1.

Case 4b: Suppose that 5 | 12k − 3, 7 | 12k − 3, and 11 ∤ 12k − 3.

Use the labeling ℓ in Equation (1) with the following four redefined labels:

ℓ(v_{5k}) = 12k − 1, ℓ(u_{5k}) = 12k − 3, ℓ(u_{5k+2}) = 12k + 8, ℓ(v_{5k+4}) = 12k + 4. (6)

Since the two vertices indexed by 5k are in the previous block of ten vertices, it is important to consider whether that block falls within a case in which any labels were swapped from the initial labeling of that block. Since we assume 5 | 12k − 3, then 5 | 12k − 13, which is equal to 12(k − 1) − 1. Whereas 7 | 12k − 3 implies 7 ∤ 12k − 15, which is equal to 12(k − 1) − 3. Therefore, vertices in U_{k−1} ∪ V_{k−1} would be labeled according to Case 3a. Neither vertex whose label was swapped within Case 3a is adjacent to v_{5k} or u_{5k}, so the adjacent pairs of labels to consider from that block are 12k − 3 and 12k − 2, 12k − 3 and 12k − 1, and 12k − 1 and 12k − 4.

Overall, there are ten adjacent pairs of labels that need to be verified as relatively prime. It is clear that

gcd(12k−3, 12k−2) = gcd(12k−3, 12k−1) = gcd(12k+7, 12k+8) = gcd(12k+4, 12k+5) = 1.

Since the only reassigned label that is a multiple of 3 is 12k − 3, we have

gcd(12k − 4, 12k − 1) = gcd(12k − 1, 12k + 2) = gcd(12k + 4, 12k + 7) = 1.

The assumption 5 | 12k − 3 implies 5 is not a factor of 12k + 8 or 12k + 4, hence

gcd(12k + 3, 12k + 8) = gcd(12k + 4, 12k + 9) = 1.

Finally, by our assumption that 11 ∤ 12k − 3, we know gcd(12k − 3, 12k + 8) = 1.

Case 4c: Suppose that 5 | 12k − 3, 7 | 12k − 3, 11 | 12k − 3, and 13 ∤ 12k − 3. Use the labeling ℓ in Equation (1) with the following five redefined labels:

\begin{matrix}ℓ(v_{5k}) = 12k − 1, & ℓ(u_{5k}) = 12k − 3, & ℓ(u_{5k+2}) = 12k + 10, \\ ℓ(u_{5k+3}) = 12k + 8, & ℓ(v_{5k+4}) = 12k + 4. \end{matrix}  (7)

We can change the labels on v_{5k} and u_{5k} without causing any adjacent pairs of vertices to not be relatively prime by the same reasoning as given in Case 4a. There are ten additional pairs of labels that need to be shown to be relatively prime to complete this case. Clearly,

gcd(12k − 1, 12k + 2) = gcd(12k + 4, 12k + 5) = gcd(12k + 7, 12k + 10)
= gcd(12k + 5, 12k + 8) = gcd(12k + 8, 12k + 11)
= gcd(12k + 4, 12k + 7) = 1.

By our assumption that 5 | 12k − 3, we know 5 is not a factor of 12k + 4, resulting in gcd(12k + 4, 12k + 9) = 1. Similarly, 7 is assumed to be a factor of 12k − 3, so 7 ∤ 12k + 3 and 7 ∤ 12k + 8; therefore, gcd(12k + 3, 12k + 10) = gcd(12k + 1, 12k + 8) = 1. Lastly, we assumed 13 ∤ 12k − 3, hence gcd(12k − 3, 12k + 10) = 1, resulting in the relatively prime condition being satisfied.

Case 4d: Suppose that 5 | 12k − 3, 7 | 12k − 3, 11 | 12k − 3, and 13 | 12k − 3.

Use the labeling ℓ in Equation (1) with the following two redefined labels: u_{5k−2} as 12k + 2 and v_{5k+1} as 12k − 2. As in the last two cases, the previous block of vertices that contains u_{5k−2} falls within Case 3a, which involves swapping two labels on vertices that are not adjacent to u_{5k−2}. Its neighbors then are labeled by 12k − 11, 12k − 7, and 12k − 1, while the label 12k − 2 on v_{5k+1} is adjacent to 12k − 3, 12k + 1, and 12k + 3. Thus, by our assumptions in this case, our reassigned labels are relatively prime with the labels of adjacent vertices.

Note that it is only possible for 5 to divide at most one value of 12k − 1, 12k − 3, and 12k + 5 since none of the differences between pairs of these values are a multiple of 5. The four possibilities this leaves are that 5 divides none of these three values (Case 1), 5 only divides 12k+5 (Case 2), 5 only divides 12k−1 (Cases 3a and 3b depending on the divisibility of this value by 7), and 5 only divides 12k − 3 (Case 4a-4d depending on if the next three prime numbers divide this value). Hence our eight cases are sufficient to cover all possible situations.

Therefore, by our assumptions and case analysis, it is clear that all labels are relatively prime with their adjacent labels. Thus in each case the updated ℓ is a coprime labeling, making 𝔭𝔯(GP(5m, 2)) ≤ 12m − 1. Since α(GP(5m, 2)) = ⌊\frac{4(5m)}{5}⌋ = 4m, we need 6m odd numbers to label the vertices in GP(5m, 2). Thus, 𝔭𝔯(GP(5m, 2)) ≥ 12m − 1. Therefore, 𝔭𝔯(GP(5m, 2)) = 12m − 1.

Theorem 10. The minimum coprime number for GP(n, 2) for n ≥ 5 is given by

𝔭𝔯(GP(n, 2)) = \begin{cases}12m − 1, & if n = 5m; \\ 12m + 3, & if n = 5m + 1; \\ 12m + 5, & if n = 5m + 2; \\ 12m + 7, & if n = 5m + 3; \\ 12m + 9, & if n = 5m + 4. \end{cases}

Proof. When n = 5m, we constructed in Lemma 9 a minimum coprime labeling ℓ with 12m − 1 as the largest label. For the remaining four cases, we will build the labeling by using ℓ defined in Lemma 9 for the first 5m vertices in v_{1} … v_{n} and the first 5m vertices in u_{1} … u_{n}. Note that the vertices v_{5m}, u_{5m}, and u_{5m−1} are not changed from the labeling defined in Equation (1). Hence, ℓ(v_{5m}) = 12m−3, ℓ(u_{5m}) = 12m−1, and ℓ(u_{5m−1}) = 12m−5.

Case 1: Suppose that n = 5m + 1. Label the remaining vertices as ℓ(u_{5m+1}) = 12m + 3 and ℓ(v_{5m+1}) = 12m + 1. By Lemma 9, we need only check that the following pairs of adjacent vertices have relatively prime labels: u_{5m}u_{1}, v_{5m+1}v_{1}, u_{5m+1}u_{2}, u_{5m+1}v_{5m+1}, u_{5m−1}u_{5m+1}, and v_{5m}v_{5m+1}. It is clear we have each of the following necessary relatively prime pairs:

gcd(1, 12m − 1) = gcd(2, 12m + 1) = gcd(4, 12m + 3) = gcd(12m + 1, 12m + 3)
= gcd(12m − 5, 12m + 3) = gcd(12m − 3, 12m + 1) = 1.

Since the independence number is α(GP(5m + 1, 2)) = ⌊\frac{4(5m+1)}{5}⌋ = 4m, we have used the maximum number of even labels less than 12m + 3. Since all odd integers were used from 1 to 12m + 3, we have that 𝔭𝔯(GP(n, 2)) = 12m + 3 when n = 5m + 1.

Case 2: We now suppose that n = 5m+2. We label the vertices v_{1}, …, v_{5m} and u_{1}, …, u_{5m} as in Lemma 9. Label the remaining vertices as

ℓ(u_{5m+1}) = 12m + 4, ℓ(u_{5m+2}) = 12m + 5, ℓ(v_{5m+1}) = 12m + 1, ℓ(v_{5m+2}) = 12m + 3.

As explained above, ℓ(u_{5m}) = 12m − 1, ℓ(v_{5m}) = 12m − 3, and ℓ(u_{5m−1}) = 12m − 5. Also note that our new labels on vertices adjacent v_{1}, u_{1}, and u_{2} make relatively prime pairs since ℓ(u_{5m+2}) and ℓ(v_{5m+2}) are odd. For the remaining adjacent pairs, we have

gcd(12m − 5, 12m + 4) = gcd(12m + 1, 12m + 4) = gcd(12m − 1, 12m + 5)
= gcd(12m + 3, 12m + 5) = gcd(12m − 3, 12m + 1)
= gcd(12m + 1, 12m + 3) = 1.

The independence number in this case is α(GP(5m + 2, 2)) = ⌊\frac{4(5m+2)}{5}⌋ = 4m + 1, which shows we used the maximum number of even labels since one of the last four vertex labels is even. Thus, we have that 𝔭𝔯(GP(n, 2)) = 12m + 5 when n = 5m + 2.

Case 3: We next suppose that n = 5m + 3. Again we label the vertices v_{1}, …, v_{5m} and u_{1}, …, u_{5m} as in Lemma 9. Label the remaining vertices as

\begin{matrix}ℓ(v_{5m+1}) = 12m + 1, & ℓ(v_{5m+2}) = 12m + 2, & ℓ(v_{5m+3}) = 12m + 5, \\ ℓ(u_{5m+1}) = 12m + 4, & ℓ(u_{5m+2}) = 12m + 3, & ℓ(u_{5m+3}) = 12m + 7. \end{matrix}

Since ℓ(v_{5m+3}) and ℓ(u_{5m+3}) are odd, they are relatively prime with ℓ(v_{1}) and ℓ(u_{2}), respectively. The remaining adjacent pairs satisfy the following:

gcd(12m − 5, 12m + 4) = gcd(12m + 1, 12m + 4) = gcd(12m + 4, 12m + 7)
= gcd(12m − 1, 12m + 3) = gcd(12m + 2, 12m + 3)
= gcd(12m + 5, 12m + 7) = gcd(12m − 3, 12m + 1)
= gcd(12m + 1, 12m + 2) = gcd(12m + 2, 12m + 5) = 1.

The independence number when n = 5m + 3 is α(GP(5m + 3, 2)) = ⌊\frac{4(5m+3)}{5}⌋ = 4m + 2, implying our use of two even labels on the final six vertices is the maximum allowable. Therefore, we have that 𝔭𝔯(GP(n, 2)) = 12m + 7 when n = 5m + 3.

Case 4: Finally, we suppose that n = 5m + 4. We need to consider three cases when labeling the final eight vertices. In each case, the labels on u_{5m+3}, u_{5m+4}, and v_{5m+4} trivially have no common factors with their respective adjacent vertices u_{1}, u_{2}, and v_{1}. First, assume 5 ∤ 12m + 2 and label the remaining vertices as

\begin{matrix}ℓ(v_{5m+1}) = 12m + 1, & ℓ(v_{5m+2}) = 12m + 5, ℓ(v_{5m+3}) = 12m + 2, & ℓ(v_{5m+4}) = 12m + 7, \\ ℓ(u_{5m+1}) = 12m + 4, & ℓ(u_{5m+2}) = 12m + 8, ℓ(u_{5m+3}) = 12m + 3, & ℓ(u_{5m+4}) = 12m + 9. \end{matrix} (8)

As before, v_{5m}, u_{5m}, and u_{5m−1} are all constructed the same as in Equation (1). Thus,

gcd(12m − 5, 12m + 4) = gcd(12m + 3, 12m + 4) = gcd(12m + 1, 12m + 4)
= gcd(12m − 1, 12m + 8) = gcd(12m + 5, 12m + 8)
= gcd(12m + 8, 12m + 9) = gcd(12m + 2, 12m + 3)
= gcd(12m + 7, 12m + 9) = gcd(12m − 3, 12m + 1)
= gcd(12m + 1, 12m + 5) = gcd(12m + 2, 12m + 5) = 1.

Additionally, our final pair satisfies gcd(12m + 2, 12m + 7) = 1 by our assumption of 5 ∤ 12m + 2.

Next we assume 5 | 12m + 2 and 7 ∤ 12m + 2. We label the eight vertices in the final block as in Equation (8) except reassign ℓ(u_{5m+1}) = 12m + 2 and ℓ(v_{5m+3}) = 12m + 4. The following show these two vertices have labels that are relatively prime with their neighbors, where the assumption of 7 ∤ 12m + 2 is necessary for the second line of gcd calculations:

v_{5m+3} : gcd(12m + 4, 12m + 5) = gcd(12m + 3, 12m + 4) = gcd(12m + 4, 12m + 7) = 1,
u_{5m+1} : gcd(12m − 5, 12m + 2) = gcd(12m + 2, 12m + 3) = gcd(12m + 1, 12m + 2) = 1.

Finally, we assume 5 | 12m + 2 and 7 | 12m + 2. We label the vertices as follows:

\begin{matrix}ℓ(v_{5m+1}) = 12m + 5 & ℓ(v_{5m+2}) = 12m + 3 & ℓ(v_{5m+3}) = 12m + 4 & ℓ(v_{5m+4}) = 12m + 9, \\ ℓ(u_{5m+1}) = 12m & ℓ(u_{5m+2}) = 12m + 2 & ℓ(u_{5m+3}) = 12m + 7 & ℓ(u_{5m+4}) = 12m + 1. \end{matrix}

Since 12m+2 is divisible by 5 and 7, we know that 12m is not divisible by 5 or 7 and likewise 12m + 4 is not divisible by 5, resulting in

gcd(12m − 5, 12m) = gcd(12m, 12m + 5) = gcd(12m, 12m + 7) = gcd(12m + 4, 12m + 9) = 1.

The remaining adjacent pairs have relatively prime labels based on the following:

gcd(12m − 1, 12m + 2) = gcd(12m + 1, 12m + 2) = gcd(12m + 2, 12m + 3)
= gcd(12m + 4, 12m + 7) = gcd(12m + 1, 12m + 9)
= gcd(12m − 3, 12m + 5) = gcd(12m + 3, 12m + 5)
= gcd(12m + 3, 12m + 4) = 1.

In all three cases for the final eight vertices, our relatively prime condition is true while using three even labels in this block. Since the independence number when n = 5m + 4 is α(GP(5m + 4, 2)) = ⌊\frac{4(5m+4)}{5}⌋ = 4m + 3, we have that 𝔭𝔯(GP(n, 2)) = 12m + 9 when n = 5m + 4, concluding our fifth and final case of n modulo 5.

We conclude this section with conjectures for the minimum coprime number of GP(n, k) for larger cases of k. The independence number for the case of k = 3 when n is odd is α(GP(n, 3)) = n − 2, and when n = 3k we have α(GP(3k, k)) = ⌈\frac{5k−2}{2}⌉, see [2, 6]. These values lead to the following conjectures, which we have verified for small values of n, although a minimum coprime labeling in each general case still alludes us.

Conjecture 11. For n ≥ 7, the minimum coprime number for GP(n, 3) if n is odd is

𝔭𝔯(GP(n, 3)) = 2n + 3.

Conjecture 12. For k ≥ 2, the minimum coprime number for GP(3k, k) is given by

𝔭𝔯(GP(3k, k)) = \begin{cases}7k, & if k is odd; \\ 7k + 1, & if k is even. \end{cases}

5 Stacked prisms

We next turn our focus to the class of graphs known as the stacked prism, also known as the generalized prism graph. A stacked prism is defined as Y_{m,n} = C_{m}□P_{n} for m ≥ 3 and n ≥ 1. See Figure 4 for an example of Y_{3,6} with a minimum coprime labeling.

Figure 4: Example of a minimum coprime labeling of Y_{3,6}

We first focus on the stacked triangular prism, Y_{3,n}, which has 3n vertices. Its independence number is n since an independent set can contain at most one vertex from each triangle, and it is trivial to find such a set of n vertices. We demonstrate in the following result a way to apply a minimum coprime labeling based on how this independence number limits our use of even labels.

Theorem 13. The minimum coprime number for the stacked triangular prism is given by

𝔭𝔯(Y_{3,n}) = 4n − 1.

Proof. We refer to the vertices of Y_{3,n} as v_{i,j} where i = 1, …, n and j = 1, 2, 3. Then the edges of the graph are of the form v_{i,j}v_{i+1,j} and v_{i,j}v_{i,k} for j ≠ k. We form a coprime labeling ℓ recursively by labeling the vertices on the (i + 1)^{st} triangle with ℓ(v_{i+1,r}), ℓ(v_{i+1,s}), ℓ(v_{i+1,t}) based on the labels chosen for the i^{th} triangle, ℓ(v_{i,r}), ℓ(v_{i,s}), ℓ(v_{i,t}). First assign the labels ℓ(v_{1,1}) = 1, ℓ(v_{1,2}) = 2, and ℓ(v_{1,3}) = 3. Each subsequent (i + 1)^{st} triangle for 1 ≤ i ≤ n − 1 will use the labels 4i + 1, 4i + 2, and 4i + 3 in some order (or 4i, 4i + 1, and 4i + 3 in one case) depending on which labels from the ith triangle are multiples of 3 and/or 5. In each case we assume ℓ(v_{i,r}) = 4i − 3, ℓ(v_{i,s}) = 4i − 2, and ℓ(v_{i,t}) = 4i − 1.

Case 1: Suppose 5 ∤ 4i − 3 and 3 ∤ 4i − 2. In this case, we assign ℓ(v_{i+1,r}) = 4i + 2, ℓ(v_{i+1,s}) = 4i + 1, and ℓ(v_{i+1,t}) = 4i + 3. The three edges within the (i + 1)^{st} triangle have relatively prime labels since they are either consecutive integers or consecutive odd integers. Since we assumed 5 ∤ 4i − 3 and 3 ∤ 4i − 2, the edges between the i^{th} and (i + 1)^{st} triangle satisfy the following:

gcd(4i − 3, 4i + 2) = gcd(4i − 2, 4i + 1) = gcd(4i − 1, 4i + 3) = 1.

Case 2: Assume 5 | 4i − 3 and 3 ∤ 4i − 1, which implies 5 ∤ 4i − 2. We then assign ℓ(v_{i+1,r}) = 4i + 1, ℓ(v_{i+1,s}) = 4i + 3, and ℓ(v_{i+1,t}) = 4i + 2. Again the vertices within the newly labeled triangle have pairs of relatively prime labels. Since 5 ∤ 4i − 2 and 3 ∤ 4i − 1, the edges between the two triangles satisfy the following:

gcd(4i − 3, 4i + 1) = gcd(4i − 2, 4i + 3) = gcd(4i − 1, 4i + 2) = 1.

Case 3: Next suppose 5 ∤ 4i − 3 and 5 ∤ 4i − 2, in which we assign ℓ(v_{i+1,r}) = 4i + 2, ℓ(v_{i+1,s}) = 4i + 3, and ℓ(v_{i+1,t}) = 4i + 1. As in previous cases, we only need to verify the edges between the i^{th} and (i + 1)^{st} triangles have relatively prime labels on their endpoints, which is satisfied since our assumptions of 5 ∤ 4i − 3 and 5 ∤ 4i − 2 result in

gcd(4i − 3, 4i + 2) = gcd(4i − 2, 4i + 3) = gcd(4i − 1, 4i + 1) = 1.

Case 4: There are two remaining other possible assumptions that can be made about factors of 3 or 5 that would allow all cases to be covered: either 5 | 4i − 3 and 3 | 4i − 1, or 5 ∤ 4i − 3 and both 3 and 5 divide 4i−2. We handle these by combining them into one final case. This is because if 5 | 4i − 3 and 3 | 4i − 1, then this implies 5 ∤ 4i + 1 and 3, 5 | 4i + 2. Therefore, having the first of these possible cases implies the second occurs on the next triangle, so we assign labels to the (i + 1)^{st} and (i + 2)^{nd} triangles at once while assuming 5 | 4i − 3 and 3 | 4i − 1. We set ℓ(v_{i+1,r}) = 4i, ℓ(v_{i+1,s}) = 4i + 1, and ℓ(v_{i+1,t}) = 4i + 3, as well as ℓ(v_{i+2,r}) = 4i + 5, ℓ(v_{i+2,s}) = 4i + 6, and ℓ(v_{i+2,t}) = 4i + 7. Note that the labels on one of the edges of the (i + 1)^{st} do not trivially satisfy the relatively prime condition. However, gcd(4i, 4i+3) = 1 since the assumption of 3 | 4i−1 implies 3 ∤ 4i, so the condition is satisfied nonetheless. Also note that while the (i + 1)^{st} triangle does not use the three consecutive labels that have been used in other cases, the (i+2)^{nd} triangle does use the three consecutive values that allow us to continue with our recursion to find the (i + 3)^{rd} triangle next.

We now verify the six edges from the i^{th} triangle to the (i + 1)^{st} and the (i + 1)^{st} triangle to the (i + 2)^{nd} have relatively prime endpoints. It is clear that gcd(4i − 1, 4i + 3) = gcd(4i + 3, 4i + 7) = 1. Since we assumed 3 | 4i − 1, we know 3 ∤ 4i − 2 or 4i, hence gcd(4i − 2, 4i + 1) = gcd(4i − 3, 4i) = 1. Our assumption of 5 | 4i − 3 implies 5 ∤ 4i or 4i + 1, thus resulting in gcd(4i, 4i + 5) = gcd(4i + 1, 4i + 6) = 1.

In all four cases, we have verified that each pair of adjacent vertices is labeled by relatively prime integers, thus resulting in a coprime labeling once our recursion approach reaches i = n − 1. The final triangle will use 4(n − 1) + 3 = 4n − 1 as its largest label. Thus, since we used the maximum amount of n even labels based on the independence number and the smallest possible odd labels, we have proven 𝔭𝔯(Y_{3,n}) = 4n − 1.

We next investigate a minimum coprime labeling of the stacked pentagonal prism, Y_{5,n}, which has 5n vertices. Similarly to Y_{3,n}, its independence number is determined based on at most 2 independent vertices being on each pentagon. Thus, the independence number is α(Y_{5,n}) = 2n, which leads to the following result on the minimum coprime number of the stacked pentagonal prism. See Figure 5 for an example of Y_{5,6} with a minimum coprime labeling.

Figure 5: Example of a minimum coprime labeling of Y_{5,6}

Theorem 14. The minimum coprime number for the stacked pentagonal prism graph is

𝔭𝔯(Y_{5,n}) = 6n − 1.

Proof. We will call v_{i,j} the vertices of Y_{5,n} where i = 1, …, n and j = 1, 2, 3, 4, 5. We initially assign a labeling ℓ for i = 1, …, 70 as follows if i is odd:

ℓ(v_{i,1}) = 6i − 3, ℓ(v_{i,2}) = 6i − 4, ℓ(v_{i,3}) = 6i − 5, ℓ(v_{i,4}) = 6i − 2, ℓ(v_{i,5}) = 6i − 1,

and using the following if i is even:

ℓ(v_{i,1}) = 6i − 5, ℓ(v_{i,2}) = 6i − 1, ℓ(v_{i,3}) = 6i − 2, ℓ(v_{i,4}) = 6i − 3, ℓ(v_{i,5}) = 6i − 4.

Since the labeling differs on odd- and even-indexed pentagons, there are twenty types of adjacent pairs to consider as having relatively labels. If i is odd and k is even, the edges v_{i,1}v_{i,2}, v_{i,2}v_{i,3}, v_{i,4}v_{i,5}, v_{k,2}v_{k,3}, v_{k,3}v_{k,4}, v_{k,4}v_{k,5}, and v_{k,5}v_{k,1} are labeled by consecutive integers. The edges v_{i,5}v_{i,1}, v_{i,1}v_{i+1,1}, v_{k,1}v_{k,2}, and v_{k,1}v_{k+1,1} are labeled by odd integers that have a difference of 2, 4, or 8. Edges of the form v_{i,3}v_{i,4}, v_{i,2}v_{i+1,2}, v_{i,3}v_{i+1,3}, v_{i,5}v_{i+1,5}, v_{k,2}v_{k+1,2}, v_{k,3}v_{k+1,3}, or v_{k,5}v_{k+1,5} have labels that differ by 3 or 9, in which these labels are not multiples of 3. At this point, we have shown that the vertices on eighteen edges are relatively prime.

The edges v_{i,4}v_{i+1,4} and v_{k,4}v_{k+1,4} have labels that differ by 5 and 7, respectively, and hence may not be relatively prime for certain i and k. Rather than detail numerous cases of alterations that need to be made to the labeling to fix these, we instead list the reassigned labels of 46 vertices from the 350 labels in which i = 1, …, 70, as seen in Table 2. The labels in bold are the 46 that were reassigned to avoid adjacent labels sharing multiples of 5 and 7.

3  2 1  4  5 7 11 10 9  8 15 16 13 14 17 19 21 22 23 20 27 26 25 28 29 31 35 34 33 32 39 38 37 40 41 43 45 46 47 44 51 52 49 50 53 55 59 58 57 56 63 62 61 64 65 67 71 70 69 68 75 74 73 76 77 79 83 82 81 80 87 86 85 88 89 91 95 94 93 92 101 98 97 100 99 105 107 106 103 104 113 110 109 112 111 115 119 118 117 116 123 122 121 124 125 127 131 130 129 128 135 134 133 136 137 139 143 142 141 140 147 146 145 148 149 151 153 154 155 152 159 160 157 158 161 163 167 166 165 164 171 170 169 172 173 175 179 178 177 176 183 184 181 182 185 187 189 190 191 188 195 194 193 196 197 199 203 202 201 200 207 206 205 208 209 211 213 214 215 212 219 220 217 218 221 223 227 226 225 224 231 230 229 232 233 235 239 238 237 236 243 242 241 244 245 247 251 250 249 248 255 254 253 256 257 259 263 262 261 260 267 268 265 266 269 275 273 274 271 272 279 278 277 280 281 287 285 286 283 284 291 292 289 290 293 295 299 298 297 296 303 302 301 304 305 307 311 310 309 308 315 314 313 316 317 319 323 322 321 320 327 326 325 328 329 331 335 334 333 332 339 338 337 340 341 343 345 346 347 344 351 352 349 350 353 355 357 358 359 356 363 362 361 364 365 367 371 370 369 368 375 374 373 376 377 379 383 382 381 380 387 386 385 388 389 391 395 394 393 392 399 398 397 400 401 403 405 406 407 404 411 412 409 410 413 415 419 418 417 416

Table 2: Labeling of the Stacked Pentagon for i = 1 to 70

Using a computer, we have verified that each reassigned label is relatively prime with any adjacent label, resulting in a coprime labeling of the graph up to n = 70. Another important fact that can be observed is that the largest difference between adjacent labels is 10.

To label the stacked pentagonal prism graph when n > 70, we assign for i > 70 and j = 1, … 5 the label ℓ(v_{i,j}) = ℓ(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 ≥ 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:

{ℓ(v_{70m,1}) = 420m − 5, ℓ(v_{70m+1,1}) = 420m + 3},
{ℓ(v_{70m,2}) = 420m − 1, ℓ(v_{70m+1,2}) = 420m + 2},
{ℓ(v_{70m,3}) = 420m − 2, ℓ(v_{70m+1,3}) = 420m + 1},
{ℓ(v_{70m,4}) = 420m − 3, ℓ(v_{70m+1,4}) = 420m + 4},
{ℓ(v_{70m,5}) = 420m − 4, ℓ(v_{70m+1,5}) = 420m + 5}.

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 ≥ 71 as well.

Note that the largest label ℓ(v_{i,j}) for j = 1, …, 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 𝔭𝔯(Y_{5,n}) = 6n − 1.

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 α(C_{2k+1}) = k, one can observe that α(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.

Conjecture 15. The minimum coprime number for stacked (2k + 1)-gon prism graph is

𝔭𝔯(Y_{2k+1,n}) = 2(k + 1)n − 1.

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 α(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.

6 Variation of generalized Petersen graphs

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}, …, v_{2k} and u_{1}, …, 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, …, 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 6.

Theorem 16. For the graph GP^{∗}(2k, k) in which k ≥ 2, we have the following:

1. GP^{∗}(2k, k) is prime if k is odd,

2. 𝔭𝔯(GP^{∗}(2k, k)) = 4k + 1 if k is even.

Proof. We first assume k is odd. We begin by labeling the vertices of GP^{∗}(2k, k) as follows:

ℓ(v_{i}) = \begin{cases}4i − 3, & for i = 1, 3, 5, …, k; \\ 4i, & for i = 2, 4, 6, …, k − 1; \\ 4i − 4k, & for i = k + 1, k + 3, k + 5, …, 2k; \\ 4i − 3 − 4k, & for i = k + 2, k + 4, k + 6, …, 2k − 1; \end{cases}  (9)

ℓ(u_{i}) = \begin{cases}4i − 2, & for i = 1, 3, 5, …, k; \\ 4i − 1, & for i = 2, 4, 6, …, k − 1; \\ 4i − 1 − 4k, & for i = k + 1, k + 3, k + 5, …, 2k; \\ 4i − 2 − 4k, & for i = k + 2, k + 4, k + 6, …, 2k − 1. \end{cases}

Figure 6: Examples of a prime labeling of GP^{∗}(18, 9) on the left and a minimum coprime labeling of GP^{∗}(20, 10) on the right.

For the pairs v_{i}v_{i+1} and v_{i+k}v_{i+1+k} for i ∈ {1, …, k−1}, it is clear that gcd(ℓ(v_{i}), ℓ(v_{i+1})) ∈ {1, 7} and gcd(ℓ(v_{i+k}), ℓ(v_{i+k+1})) ∈ {1, 7}. Notice that gcd(ℓ(v_{k}), ℓ(v_{k+1})) = gcd(4k − 3, 4) = 1 and gcd(ℓ(v_{2k}), ℓ(v_{1})) = gcd(4k − 1, 1) = 1. For the edges u_{i}u_{i+k}, it is easily verified that when i ∈ {1, 3, …, k},

gcd(ℓ(u_{i}), ℓ(u_{i+k})) = gcd(4i − 2, 4(i + k) − 1 − 4k) = gcd(4i − 2, 4i − 1) = 1.

Similarly, gcd(ℓ(u_{i}), ℓ(u_{i+k})) = 1 when i ∈ {2, 4, …, k − 1} and gcd(ℓ(u_{i}), ℓ(v_{i})) = 1 for all i = 1, …, 2k since these pairs are consecutive integers. Thus, our only concern with the labeling is when ℓ(v_{i}) and ℓ(v_{i+1}) are both divisible by 7. We handle these instances by breaking the proof into several cases based on the remainder of ℓ(v_{i})/3 and whether or not 5 divides ℓ(v_{i}) + 2. For the sake of simplicity, let ℓ(v_{i}) = a where i ∈ {1, 3, …, k − 2, k + 2, k + 4, …, 2k − 1}. Notice that in our labeling, ℓ(v_{i}) = a is odd in these cases in which ℓ(v_{i+1}) − ℓ(v_{i}) = 7. In each of the cases below, we are assuming that a ≡ 0 (mod 7).

Case 1: Suppose that a ≡ 1 (mod 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.

Case 2: Suppose that a ≡ 0 (mod 3) and 5 ∤ 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.

Case 3: Suppose that a ≡ 0 (mod 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 ≡ 0 (mod 15), gcd(a − 8, a + 7) = 1. Therefore, the reassigned labels are relatively prime with any newly adjacent label.

Case 4: Suppose that a ≡ 2 (mod 3) and 5 ∤ 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.

Case 5: Suppose that a ≡ 2 (mod 3) and 5 | 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 ≡ 2 (mod 3), a + 2 ≡ 0 (mod 5), and a ≡ 0 (mod 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 ℓ(v_{i+2}) = a + 8 in the original labeling of the vertices, then since a is odd, a ≡ 2 (mod 3), and a + 2 ≡ 0 (mod 5), it follows that gcd(a + 15, a) = 1. Since k is odd, it is not possible for ℓ(v_{i+2}) to be 4. It is possible that ℓ(v_{i+2}) = 1 in the case of i = 2k − 1, but in this case, ℓ(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 𝔭𝔯(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 α(GP^{∗}(2k, k)). An independent set can contain at most k vertices from the k-cycle formed by the vertices v_{1}, …, 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}, …, 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}, …, 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}, …, u_{2k} since only one of u_{i} or u_{i+k} can be included for each i = 1, …, k. Hence we cannot create an independent set of size 2k, showing that α(GP^{∗}(2k, k)) < 2k = \frac{1}{2}|V |. Therefore, by Lemma 1, 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 ℓ similar our odd case, defined by the following:

ℓ(v_{i}) = \begin{cases}4i − 3, & for i = 1, 3, 5, …, k − 1; \\ 4i, & for i = 2, 4, 6, …, k − 2; \\ 4i − 4k, & for i = k + 1, k + 3, k + 5, …, 2k − 1; \\ 4i − 3 − 4k, & for i = k + 2, k + 4, k + 6, …, 2k; \end{cases}  (10)

ℓ(u_{i}) = \begin{cases}4i − 2, & for i = 1, 3, 5, …, k − 1; \\ 4i − 1, & for i = 2, 4, 6, …, k; \\ 4i − 1 − 4k, & for i = k + 1, k + 3, k + 5, …, 2k − 1; \\ 4i − 2 − 4k, & for i = k + 2, k + 4, k + 6, …, 2k. \end{cases}

Note that the label for v_{k} was not listed in Equation (10) since continuing the pattern ℓ(v_{i}) = 4i for even i would assign it as ℓ(v_{k}) = 4k, which is not relatively prime with its neighboring label ℓ(v_{k+1}) = 4. Hence we instead assign ℓ(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 ℓ 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 ℓ(v_{k}) and its neighbors are not involved in the alterations to ℓ. The only situation in which any of the five cases involve swapping these labels would be if a = ℓ(v_{k−1}). However, with ℓ(v_{k}) = 4k + 1, we have ℓ(v_{k}) − ℓ(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 𝔭𝔯(GP^{∗}(2k, k)) = 4k + 1.

A Additional generalized Petersen results

For Theorems 17–23, 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 2. Recall that we are working under the assumption that n is odd for the following theorems.

Theorem 17. If n + 4 is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We may assume n ≢ 2 (mod 3), otherwise n + 4 would be divisible by 3 and hence not prime. If n ≡ 0 (mod 3), then we use the labeling defined in Table 3. If n ≡ 1 (mod 3), then we alter the previous labeling and instead use the labeling defined in Table 4.

Theorem 18. If n − 2 is prime and n > 5, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We may assume n ≢ 2 (mod 3) to avoid n−2 being a multiple of 3. If n ≡ 0 (mod 3), then we use the labeling defined in Table 5. If n ≡ 1 (mod 3), we instead label the graph using the labeling in Table 6. 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.

Theorem 19. If n − 4 is prime and n > 7, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We may assume n ≢ 1 (mod 3), else n − 4 is a multiple of 3. If n ≡ 0 (mod 3), then we use the labeling defined in Table 7. If n ≡ 2 (mod 3), then use the same labeling defined in Table 8.

Theorem 20. If 2n + 3 is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We may assume n ≢ 0 (mod 3) to avoid 2n+3 being divisible by 3. If n ≡ 1 (mod 3), then we use the labeling defined in Table 9. If n ≡ 2 (mod 3), then use the same labeling defined in Table 10 except n + 1 is labeled as n − 1 instead.

Theorem 21. If 2n − 3 is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We may assume n ≢ 0 (mod 3), otherwise 2n−3 is a multiple of 3. If n ≡ 2 (mod 3), then we use the labeling defined in Table 11. If n ≡ 1 (mod 3), then we use the labeling defined in Table 12.

Theorem 22. If 2n − 5 is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We may assume n ≢ 1 (mod 3) to avoid 3 dividing into 2n−5. If n ≡ 0 or 2 (mod 3) and n ≡ 1, 2, or 4 (mod 5), then we use the labeling defined in Table 13. When n ≡ 0 or 2 (mod 3) and n ≡ 0 (mod 5), then 2n − 5 ≡ 0 (mod 5), so we ignore these cases. When n ≡ 0 (mod 3) and n ≡ 3 (mod 5), then we use the labeling defined in Table 14. When n ≡ 2 (mod 3) and n ≡ 3 (mod 5), then we use the labeling defined in Table 15.

Theorem 23. If n + 6 is prime, then 𝔭𝔯(GP(n, 1)) = 2n + 1.

Proof. We may assume that n ≢ 0 (mod 3), otherwise n + 6 is divisible by 3. If n ≡ 1 or 2 (mod 3) and n ≡ 0, 2, or 3 (mod 5), then we use the labeling defined in Table 16. If n ≡ 2 (mod 3) and n ≡ 1 (mod 5), then we use the labeling defined in Table 17. If n ≡ 1 (mod 3) and n ≡ 1 (mod 5), then we use the labeling defined in Table 18. If n ≡ 1 or 2 (mod 3) and n ≡ 4 (mod 5), then n + 6 is divisible by 5, so these cases are removed.

\begin{matrix}1 & 2 & ⋯ & n − 3 & n − 2 & n − 1 & n \\ n + 5 & n + 6 & ⋯ & 2n + 1 & n + 1 & n + 2 & n + 4 \end{matrix}

Table 3: Labeling for Theorem 17 when n ≡ 0 (mod 3)

\begin{matrix}1 & 2 & ⋯ & n − 3 & n − 2 & n + 2 & n + 1 \\ n + 5 & n + 6 & ⋯ & 2n + 1 & n & n + 3 & n + 4 \end{matrix}

Table 4: Labeling for Theorem 17 when n ≡ 1 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & ⋯ & n − 3 & n − 2 & n − 1 & n \\ 2n − 1 & 2n + 1 & n + 1 & n + 2 & ⋯ & 2n − 5 & 2n − 2 & 2n − 3 & 2n − 4 \end{matrix}

Table 5: Labeling for Theorem 18 when n ≡ 0 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & ⋯ & n − 5 & n − 4 & n − 3 & n − 2 & n − 1 & n \\ 2n − 1 & 2n + 1 & n + 1 & n + 2 & ⋯ & 2n − 7 & 2n − 4 & 2n − 5 & 2n − 6 & 2n − 3 & 2n − 2 \end{matrix}

Table 6: Labeling for Theorem 18 when n ≡ 1 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & ⋯ & n − 7 & n − 6 & n − 5 & n − 4 & n − 3 & n − 2 & n − 1 & n \\ 2n − 3 & 2n − 1 & 2n − 2 & 2n + 1 & n + 1 & n + 2 & ⋯ & 2n − 11 & 2n − 8 & 2n − 9 & 2n − 10 & 2n − 7 & 2n − 6 & 2n − 5 & 2n − 4 \end{matrix}

Table 7: Labeling for Theorem 19 when n ≡ 0 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & ⋯ & n − 5 & n − 4 & n − 3 & n − 2 & n − 1 & n \\ 2n − 3 & 2n − 1 & 2n & 2n + 1 & n + 1 & n + 2 & ⋯ & 2n − 9 & 2n − 6 & 2n − 7 & 2n − 8 & 2n − 5 & 2n − 4 \end{matrix}

Table 8: Labeling for Theorem 19 when n ≡ 2 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & ⋯ & n − 2 & n + 1 & n + 2 \\ n & 2n + 1 & 2n & 2n − 1 & ⋯ & n + 5 & n + 4 & n + 3 \end{matrix}

Table 9: Labeling for Theorem 20 when n ≡ 1 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & ⋯ & n − 2 & n & n + 3 \\ n − 1 & 2n + 1 & 2n & 2n − 1 & ⋯ & n + 5 & n + 4 & n + 2 \end{matrix}

Table 10: Labeling for Theorem 20 when n ≡ 2 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & ⋯ & n − 2 & 2n − 3 & 2n \\ 2n − 2 & 2n − 5 & 2n − 6 & 2n − 7 & ⋯ & n − 1 & 2n − 1 & 2n + 1 \end{matrix}

Table 11: Labeling for Theorem 21 when n ≡ 2 (mod 3)

\begin{matrix}1 & 2 & 3 & 4 & ⋯ & n − 2 & 2n & 2n + 1 \\ 2n − 4 & 2n − 5 & 2n − 6 & 2n − 7 & ⋯ & n − 1 & 2n − 3 & 2n − 1 \end{matrix}

Table 12: Labeling for Theorem 21 when n ≡ 1 (mod 3)

\begin{matrix}1 & 2 & 3 & ⋯ & n − 3 & 2n − 5 & 2n + 1 & 2n \\ 2n − 6 & 2n − 7 & 2n − 8 & ⋯ & n − 2 & 2n − 3 & 2n − 2 & 2n − 1 \end{matrix}

Table 13: Labeling for Theorem 22 when n ≡ 0, 2 (mod 3) and n ≡ 1, 2, or 4 (mod 5)

\begin{matrix}1 & 2 & 3 & ⋯ & n − 3 & 2n − 5 & 2n − 1 & 2n \\ 2n − 4 & 2n − 7 & 2n − 8 & ⋯ & n − 2 & 2n − 3 & 2n − 2 & 2n + 1 \end{matrix}

Table 14: Labeling for Theorem 22 when n ≡ 0 (mod 3) and n ≡ 3 (mod 5)

\begin{matrix}1 & 2 & 3 & ⋯ & n − 3 & 2n − 5 & 2n − 1 & 2n \\ 2n − 6 & 2n − 7 & 2n − 8 & ⋯ & n − 2 & 2n + 1 & 2n − 2 & 2n − 3 \end{matrix}

Table 15: Labeling for Theorem 22 when n ≡ 2 (mod 3) and n ≡ 3 (mod 5)

\begin{matrix}1 & 2 & 3 & ⋯ & n − 5 & n − 4 & n − 3 & n − 2 & n + 2 & n + 3 \\ n + 7 & n + 8 & n + 9 & ⋯ & 2n + 1 & n + 1 & n & n − 1 & n + 4 & n + 6 \end{matrix}

Table 16: Labeling for Theorem 23 when n ≡ 1 or 2 (mod 3) and n ≡ 0, 2, or 3 (mod 5)

\begin{matrix}1 & 2 & 3 & ⋯ & n − 5 & n − 4 & n − 3 & n − 2 & n + 2 & n + 5 \\ n + 7 & n + 8 & n + 9 & ⋯ & 2n + 1 & n + 1 & n & n + 3 & n + 4 & n + 6 \end{matrix}

Table 17: Labeling for Theorem 23 when n ≡ 2 (mod 3) and n ≡ 1 (mod 5)

\begin{matrix}1 & 2 & 3 & ⋯ & n − 5 & n − 4 & n − 3 & n − 2 & n + 4 & n + 5 \\ n + 7 & n + 8 & n + 9 & ⋯ & 2n + 1 & n + 1 & n & n + 3 & n + 2 & n + 6 \end{matrix}

Table 18: Labeling for Theorem 23 when n ≡ 1 (mod 3) and n ≡ 1 (mod 5)

References

[1] J. Asplund and N. B. Fox, Minimum coprime labelings for operations on graph, Integers 19 (2019), Article A24.

[2] B. Behsaz, P. Hatami, and E. Mahmoodian, On minimum vertex covers of generalized Petersen graph, Australas. J. Combin. 40 (2008), 253–264.

[3] A. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, and C. McBee, Coprime and prime labelings of graphs, J. Integer Sequences 19 (2016), Article 16.5.8.

[4] N. Besharati, J. B. Ebrahimi, and A. Azadi, Independence number of generalized Petersen graphs, Ars Combin. 124 (2016), 239–255.

[5] N. Dean, Proof of the prime ladder conjecture, Integers 17 (2017), Article A40.

[6] J. Fox, R. Gera, and P. Stănică, The independence number for the generalized Petersen graphs, Ars Combin. 103 (2012), 439–451.

[7] H.-L. Fu and K.-C. Huang, On prime labelling, Discrete Math. 127 (1994), 181–186.

[8] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. DS6 (2020).

[9] 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.

[10] K. Haque, X. Lin, Y. Yang, and P. Zhao, On the prime labeling of generalized Petersen graphs P (n, 3), Int. J. Contemp. Math. Sci. 6 (2011), 1783–1800.

[11] C. Lee, Minimum coprime graph labelings, J. Integer Sequences 23 (2020), Article 20.11.4.

[12] U. Prajapati and S. Gajjar, Prime labeling of generalized Petersen graph, Internat. J. of Math. and Soft Comput. 5 (2015), 65–71.

[13] S. Schluchter, J. Schroeder, K. Cockus, R. Ellingson, H. Harris, E. Rarity, and T. Wilson, Prime labelings of generalized Petersen graphs, Involve 10 (2017), 109–124.

[14] A. Tout, A. N. Dabboucy, and K. Howalla, Prime labeling of graphs, Nat. Acad. Sci. Lett. 11 (1982), 365–368.

2010 Mathematics Subject Classification: Primary 05C78, Secondary 11A05. Keywords: coprime labeling, prime labeling, generalized Petersen graph, prism graph.

Received July 22 2020; revised version received February 10 2021; February 14 2021. Published in Journal of Integer Sequences, February 15 2021.

Return to Journal of Integer Sequences home page.