Minimum Coprime Graph Labelings

Catherine Lee Department of Mathematics Yale University New Haven, CT 06511 USA

                    catherine.lee@yale.edu

Abstract

A coprime labeling of a graph G is a labeling of the vertices of G with distinct integers from 1 to k such that adjacent vertices have coprime labels. The minimum coprime number of G is the least k for which such a labeling exists. In this paper, we determine the minimum coprime number for a few well-studied classes of graphs, including the coronas of complete graphs with empty graphs and the joins of two paths. In particular, we resolve a conjecture of Seoud, El Sonbaty, and Mahran and two conjectures of Asplund and Fox. We also provide an asymptotic bound for the minimum coprime number of the Erdős-Rényi random graph.

1 Introduction

1.1 Background

Let G be a simple graph with n = |V (G)| vertices. A coprime labeling of G is an injection f: V (G) → {1, 2, …, k}, for some integer k ≥ n, such that if (u, v) ∈ E(G) then gcd(f(u), f(v)) = 1. The minimum coprime number 𝔭𝔯(G) is the least k for which such a labeling exists; a coprime labeling of G using only integers up to 𝔭𝔯(G) is called a minimum coprime labeling of G. If 𝔭𝔯(G) = n, then a minimum coprime labeling of G is called a prime labeling and G is a prime graph.

The notion of prime labeling originated with Entringer and was introduced in a paper by Tout, Dabboucy, and Howalla [32]. It is conceptually related to the coprime graph of integers, the graph with vertex set ℤ that contains the edge (m, n) if and only if gcd(m, n) = 1. The induced subgraph G(A) with vertex set A ⊂ {1, …, N} is called the coprime graph of A and was first studied by Erdős [8], who posed the famous problem of finding the largest set A ⊂ {1, …, N} such that K_{k} ⊄ G(A). Newman’s coprime mapping conjecture, which was proven by Pomerance and Selfridge [22], involves the existence of perfect matchings in G(A). Various other properties of the coprime graph of integers have been studied by Ahlswede and Khachatrian [1, 2, 3], Erdős [9], Erdős and A. Sárközy [10], Erdős and G. N. Sárközy [13], Erdős, A. Sárközy, and Szémeredi [11, 12], and G. N. Sárközy [26]. Further discussion of the coprime graph of integers may be found in [21].

The problem of finding a minimum coprime labeling of a graph H is equivalent to showing that H is a subgraph of the coprime graph G({1, 2, …, 𝔭𝔯(H)}). Much work has been done to prove that various classes of graphs are prime; we refer the reader to [15] for a full catalog of results. In particular, it is known that all paths, cycles, helms, fans, flowers, books, and wheels of even order are prime [15, 27, 29].

The primality of trees has been especially well studied. Entringer and Tout conjectured around 1980 that every tree is prime. While this conjecture remains open, it is now known that many classes of trees are prime, including paths, stars, caterpillars, spiders, and complete binary trees [15]. Fu and Huang [14] proved in 1994 that trees with 15 or fewer vertices are prime, and Pikhurko [20] extended this result to trees with 50 or fewer vertices in 2007. Salmasian [25] showed that any tree T with n ≥ 50 vertices satisfies 𝔭𝔯(T) ≤ 4n. Pikhurko [20] improved upon this by showing that the Entringer-Tout conjecture holds asymptotically, i.e., for any c > 0, there is an N such that for any tree T of order n > N, 𝔭𝔯(T) < (1 + c)n. In 2011, Haxell, Pikhurko, and Taraz [17] proved the Entringer-Tout conjecture for trees of sufficiently large order.

In this paper, we focus on the minimum coprime numbers of a few well-studied classes of graphs. The first class we consider is formed by taking the coronas of complete graphs and empty graphs. The corona of a graph G with a graph H, denoted G ⊙ H, is obtained by combining one copy of G with |V (G)| copies of H by attaching the i^{th} vertex in G to every vertex in the i^{th} copy of H. Tout, Dabboucy, and Howalla [32] showed that the crown graphs C_{n} ⊙ \overline{K}_{m} are prime for all positive integers n and m. The graphs K_{n} ⊙ \overline{K}_{m}, which are spanning supergraphs of the crowns C_{n} ⊙ \overline{K}_{m}, have also been studied in this context. Youssef and Elsakhawi [33] showed that K_{n} ⊙ K_{1} is prime for n ≤ 7, and K_{n} ⊙ \overline{K}_{2} is prime for n ≤ 16. Seoud, El Sonbaty, and Mahran [28] then observed that K_{n} ⊙ \overline{K}_{m} is not prime if n > π(n(m + 1) + 1). (Throughout this paper, we denote π(x) to be the number of primes less than or equal to x, and p_{n} to be the n^{th} prime number.) They also conjectured the converse,

Conjecture 1 ([28, Conjecture 3.9]). The graph K_{n} ⊙ \overline{K}_{m} is prime if n ≤ π(n(m + 1)) + 1.

They computed all values of n satisfying this condition for all m ≤ 20. Most recently, Asplund and Fox [4] computed the minimum coprime numbers of K_{n} ⊙ K_{1} and K_{n} ⊙ \overline{K}_{2}, showing that 𝔭𝔯(K_{n} ⊙ K_{1}) = p_{n−1} if n > 7 and 𝔭𝔯(K_{n} ⊙ \overline{K}_{2}) = p_{n−1} if n > 16. They conjecture that their results extend whenever n is sufficiently large relative to m.

Conjecture 2 ([4, Conjecture 1]). For all positive integers m, there exists an M > m such that for all n > M, we have𝔭𝔯(K_{n} ⊙ \overline{K}_{m}) = p_{n−1}.

We prove the following statement, which resolves Conjectures 1 and 2 affirmatively.

Theorem 3. For all positive integers m and n,

𝔭𝔯(K_{n} ⊙ \overline{K}_{m}) = max(mn + n, p_{n−1}).

The next class of graphs we consider is constructed via the join operation. The join of two disjoint graphs G and H, denoted G + H, consists of the graph union G ∪ H with edges added to connect each vertex in G to each vertex in H. We focus on the joins of two paths, which are well-studied. It was shown in [27, 28] that P_{n} + K_{1} = P_{n} + P_{1} is prime, P_{n} + \overline{K}_{2} is prime if and only if n ≥ 3 is odd, and P_{n} + \overline{K}_{m} is not prime for m ≥ 3. Asplund and Fox [4] computed the minimum coprime numbers of P_{m} + P_{n} for various m and n. They showed the following theorem.

Theorem 4 ([4, Theorems 17,18,19]). For m ≥ 4 even and n = 2, or m ≥ n and n = 3 or 4, the minimum coprime number of P_{m} + P_{n} is given by

𝔭𝔯(P_{m} + P_{n}) = \begin{cases}m + 2n − 2, & if m is odd; \\ m + 2n − 1, & if m is even. \end{cases}  (1)

They proceeded to show that (1) holds for 2 ≤ n ≤ 10 if m > 118. They conjecture that this result extends to all n as long as m is sufficiently large.

Conjecture 5 ([4, Conjecture 2]). For any positive integer N, there exists a positive integer M such that for all m > M and 2 ≤ n ≤ N, the minimum coprime number of P_{m} + P_{n} is given by

𝔭𝔯(P_{m} + P_{n}) = \begin{cases}m + 2n − 2, & if m is odd; \\ m + 2n − 1, & if m is even. \end{cases}

The k^{th} Ramanujan prime R_{k} is the least integer for which π(x) − π(\frac{x}{2}) ≥ k holds for all x ≥ R_{k}. Ramanujan primes were introduced in [23] as a generalization of Bertrand’s postulate; they are published as sequence \underline{A104272} in the On-Line Encyclopedia of Integer Sequences (OEIS) [30]. We resolve Conjecture 5 affirmatively, showing the following.

Theorem 6. For any positive integer N, if M ≥ R_{N−1} − 2N + 1, then for all m ≥ M and 2 ≤ n ≤ N, the minimum coprime number of P_{m} + P_{n} is

𝔭𝔯(P_{m} + P_{n}) = \begin{cases}m + 2n − 2, & if m is odd; \\ m + 2n − 1, & if m is even. \end{cases}

Our results on P_{m} + P_{n} automatically yield upper bounds on the minimum coprime numbers of the complete bipartite graphs K_{m,n}, and our constructions also generalize to the join of two cycles and the join of a path and a cycle, enabling us to compute 𝔭𝔯(C_{m} + C_{n}), 𝔭𝔯(C_{m} + P_{n}), and 𝔭𝔯(P_{m} + C_{n}) for sufficiently large m. Our results on these classes of graphs are given in Theorems 17 and 21, and Corollaries 22 and 23.

We conclude this paper by providing an asymptotic bound for the minimum coprime number of a random subgraph, a topic which, to the best of our knowledge, has not been previously studied. Given a graph G and p ∈ (0, 1), we obtain a probability distribution G_{p} called a random subgraph by taking subgraphs of G with each edge appearing independently with probability p. When G = K_{n}, this is called the Erdős-Rényi random graph, denoted G(n, p). We compute the following asymptotic bounds for the minimum coprime number of the Erdős-Rényi random graph.

Theorem 7. We have

𝔭𝔯(G(n, p)) ∼ n log n

almost surely, i.e., with probability tending to 1 as n → ∞.

As a corollary, we observe that

Corollary 8. For all p, G(n, p) is almost surely not prime.

1.2 Outline

In Section 2, we state several straightforward results on the minimum coprime number of an arbitrary graph which we will later use in our proofs. In Section 3, we discuss the graphs K_{n} ⊙ \overline{K}_{m}, proving Theorem 3. In Section 4, we focus on the graphs P_{m} + P_{n}, proving Theorem 6. We also consider the complete bipartite graphs K_{m,n} and the graphs C_{m} + C_{n} and C_{m} + P_{n}. In Section 5, we discuss the minimum coprime number of the Erdős-Rényi random graph, proving Theorem 7. We conclude by posing a number of open questions in coprime graph labeling in Section 6.

2 Preliminaries

In this section we state several propositions relating the minimum coprime number to other graph properties. Recall that if G and H are graphs with V (G) = V (H) and E(G) ⊆ E(H), we call H a spanning supergraph of G and G a spanning subgraph of H. The independence number α(G) of G is the size of the largest set of vertices S in V (G) such that no two vertices in S are adjacent to one another.

Proposition 9. Let G and H be graphs such that H is a spanning supergraph of G. Then 𝔭𝔯(G) ≤ 𝔭𝔯(H).

Proof. Let f : V (H) → {1, …, 𝔭𝔯(H)} be a minimum coprime labeling of H. As V (G) = V (H), f induces a coprime labeling of G. Hence 𝔭𝔯(G) ≤ 𝔭𝔯(H).

The following corollary of Proposition 9 has been noted in numerous places in the literature.

Corollary 10. Any spanning subgraph of a prime graph is prime. Any spanning supergraph of a nonprime graph is nonprime.

Proposition 11. For any graph G, 𝔭𝔯(G) ≥ 2(|V (G)| − α(G)) − 1.

Proof. Under any coprime labeling of G, the vertices with even labels must form an independent set. Hence at most α(G) even integers may be used to label G. The lower bound follows from noting that at least |V (G)| − α(G) odd integers must be used as labels.

The following corollary of Proposition 11 has been stated elsewhere in the literature, for instance in [14, 29].

Corollary 12. If G is a prime graph, then α(G) ≥ ⌊\frac{|V (G)|}{2}⌋.

3 Minimum coprime numbers of K_{n} ⊙ \overline{K}_{m}

In this section we prove Theorem 3.

Proof of Theorem 3. Set N = max(p_{n−1}, mn+n). It is apparent that 𝔭𝔯(K_{n}⊙\overline{K}_{m}) ≥ mn+n as |V (K_{n} ⊙ \overline{K}_{m})| = mn + n. By Proposition 9, we have 𝔭𝔯(K_{n} ⊙ \overline{K}_{m}) ≥ 𝔭𝔯(K_{n}). It is well known that 𝔭𝔯(K_{n}) = p_{n−1} (see [4], for example). Therefore 𝔭𝔯(K_{n} ⊙ \overline{K}_{m}) ≥ N.

It now suffices to show that it is possible to construct a coprime labeling of K_{n} ⊙ \overline{K}_{m} using only labels up to N. Denote u_{1}, …, u_{n} to be the vertices of K_{n} and v_{i,1}, …, v_{i,m} to be the vertices of the i^{th} copy of \overline{K}_{m}. Label u_{1} with 1 and the remaining u_{i} with p_{i−1}, so that we have used the first n − 1 primes as labels. We will label v_{i,1}, …, v_{i,m} with integers not exceeding mn + n, excluding 1, p_{1}, …, p_{n−1}.

After labeling the vertices of K_{n} as indicated, there are at least mn integers less than or equal to N which have not yet been used as labels. Let L_{1} denote the list of all such integers. We label the vertices v_{i+1,k} for 1 ≤ i ≤ n − 1 as follows: for each i, select the first m integers in L_{i} which are coprime to p_{i} (the label of u_{i+1}). Use these integers to label v_{i+1,1}, …, v_{i+1,m}, and remove them from L_{i} to form a new list L_{i+1}. We may use any integers in L_{n} to label v_{1,1}, …, v_{1,m}, as they are all coprime to 1, the label of u_{1}.

We claim that at each step of this process there exist m integers in L_{i} which are coprime to p_{i}, so that this process in fact yields a coprime labeling for K_{n} ⊙ \overline{K}_{m} using only integers up to N. Observe that L_{i} contains at least |L_{1}| − m(i − 1) = m(n − i + 1) elements. Suppose for the sake of contradiction that there are at most m − 1 elements in L_{i} that are coprime to p_{i}; then the remaining m(n − i) + 1 elements must all be multiples of p_{i}.

We consider the following cases. Note that by [32, 33, 4], the statement in the theorem is known for all n ≤ 3 or m ≤ 2, so we may assume that n ≥ 4 and m ≥ 3.

• If p_{i} > n, we have

p_{i} − \frac{ip_{i}}{n} + \frac{p_{i}}{mn} ≥ p_{i} − \frac{(n − 1)p_{i}}{n} + \frac{p_{i}}{mn} = \frac{p_{i}}{n} + \frac{p_{i}}{mn} > 1 + \frac{1}{m}.

• If p_{i} ≤ n and i ≥ 3, we have

p_{i} − \frac{ip_{i}}{n} + \frac{p_{i}}{mn} ≥ p_{i} − i + \frac{p_{i}}{mn} > 2 > 1 + \frac{1}{m},

as p_{i} − i ≥ 2 for all i ≥ 3.

• If p_{i} ≤ n and i = 2, we have

p_{i} − \frac{ip_{i}}{n} + \frac{p_{i}}{mn} = 3 − \frac{6}{n} + \frac{3}{mn} > \frac{3}{2} > 1 + \frac{1}{m}.

Thus, in each case, the largest integer in L_{i} is at least

p_{i}(mn − mi + 1) = mn (p_{i} − \frac{ip_{i}}{n} + \frac{p_{i}}{mn}) > mn (1 + \frac{1}{m}) = mn + n,

which is a contradiction.

4 Minimum coprime numbers of P_{m} + P_{n}

In this section we prove Theorem 6 and discuss the minimum coprime numbers of a number of graphs related to P_{m} + P_{n}. We will use the following theorem and lemma.

Theorem 13 ([19], Brun-Titchmarsh theorem). Let π(x; k, a) denote the number of primes at most x that are equivalent to a modulo k. Then

π(x + y; k, a) − π(x; k, a) ≤ \frac{2y}{φ(k) log(y/k)}

whenever y ≥ k, where φ is the Euler totient function.

Lemma 14. For all x ≥ 1, there is a prime p ∈ (x, 2x] such that p ≢ 1, 10 (mod 11).

Proof. By [24, Corollary 3 to Theorem 2], we have

π(2x) − π(x) > \frac{3}{5} \frac{x}{log x}

whenever x ≥ 20.5. Combining this with Theorem 13 shows that the total number of primes in (x, 2x] which are not congruent to 1 or 10 modulo 11 is at least

\frac{3x}{5 log x} − \frac{2x}{5(log x − log 11)}.

When x > 1331, the above expression is positive, and we have the desired result. For x ≤ 1331, we may manually verify the statement in the lemma.

Proof of Theorem 6. Set L = 2 ⌈\frac{m−1}{2}⌉ + 2n − 1. The lower bound 𝔭𝔯(P_{m} + P_{n}) ≥ L follows from Proposition 11, observing that α(P_{m}+P_{n}) = ⌈\frac{m}{2}⌉. Thus, to show that 𝔭𝔯(P_{m}+P_{n}) = L, it suffices to construct a coprime labeling using only labels up to L.

By Theorem 4, we know that such a labeling exists for n ≤ 4. Assume that n ≥ 5 and hence L ≥ R_{4} = 29. Since L ≥ R_{n−1}, we may label the vertices of P_{n} with 1 and n−1 primes between ⌈\frac{L}{2}⌉ and L, which we denote q_{1}, …, q_{n−1} in increasing order. By Lemma 14, we may assume that q_{ℓ} ≢ 1, 10 (mod 11) for some 1 ≤ ℓ ≤ n − 1. Moreover, by our assumptions on m and n, each of these primes is at least 17. As 1, q_{1}, …, q_{n−1} are each coprime to all of the other integers up to L, any coprime labeling of P_{m} using the remaining integers will yield a minimum coprime labeling for P_{m} + P_{n}.

If q_{1} > m + 1 we are done, as we may simply label the vertices of P_{m} with 2, …, m + 1 in order. Otherwise, let S_{1} be the ordered list of integers up to L, excluding {1, q_{1}, …, q_{n−1}}. We will inductively construct sets S_{i} so that |S_{i}| = L − n − i + 1 and every element less than q_{i} contained in S_{i} is coprime to its neighbors in S_{i} that are also less than q_{i}. It is clear that S_{1} satisfies the conditions above. For 1 ≤ i ≤ n − 2, we construct S_{i+1} from S_{i} as follows.

• If q_{i+1} > q_{i} + 2 and q_{i} > q_{i−1} + 2 (if i > 1), then S_{i} contains the sequence q_{i} − 2, q_{i} − 1, q_{i} + 1, q_{i} + 2, where q_{i} − 2 and q_{i} + 2 are odd and composite. Observe that 3 divides at most one of q_{i} − 2 and q_{i} + 2. If 3 ∤ q_{i} + 2, we can set S_{i+1} = S_{i} \ {q_{i} + 1}, as gcd(q_{i} − 2, q_{i} − 1) = gcd(q_{i} − 1, q_{i} + 2) = 1. Otherwise, 3 ∤ q_{i} − 2, so we can set S_{i+1} = S_{i} \ {q_{i} − 1}, as gcd(q_{i} − 2, q_{i} + 1) = gcd(q_{i} + 1, q_{i} + 2) = 1.

• If q_{i+1} = q_{i} + 2, then it suffices to set S_{i+1} = S_{i} \ {q_{i} + 1}.

• If q_{i+1} > q_{i} + 2, i > 1, and q_{i} = q_{i−1} + 2, then S_{i} contains the sequence q_{i} − 4, q_{i} − 3, q_{i} + 1, q_{i} + 2, where q_{i} − 4 and q_{i} + 2 are odd and composite. Observe that 5 divides at most one of q_{i} − 4 and q_{i} + 2. If 5 ∤ q_{i} + 2, we can set S_{i+1} = S_{i} \ {q_{i} + 1}, as gcd(q_{i} − 4, q_{i} − 3) = gcd(q_{i} − 3, q_{i} + 2) = 1 necessarily. Otherwise, 5 ∤ q_{i} − 4, so we can set S_{i+1} = S_{i} \ {q_{i} − 3}, as gcd(q_{i} − 4, q_{i} + 1) = gcd(q_{i} + 1, q_{i} + 2) = 1.

We now construct a final ordered list S_{n} ⊆ S_{n−1} such that every element in S_{n} is coprime to its neighbors. If q_{n−1} = L we are done, as we may set S_{n} = S_{n−1}. Otherwise, since L is always odd, we have q_{n−1} + 2 ≤ L, so S_{n−1} contains the sequence q_{n−1} − k − 1, q_{n−1} − k, q_{n−1} + 1, q_{n−1} + 2, where k = 1 or 3 depending on whether q_{n−1} − 2 is composite or prime respectively. As in the cases above, it is always possible to obtain S_{n} by removing one of q_{n−1} − k and q_{n−1} + 1.

If q_{n−1} = L, then we have |S_{n}| = |S_{n−1}| = L − 2n + 2 ≥ m, and we obtain a minimum coprime labeling for P_{m} + P_{n} by labeling the vertices of P_{m} with the elements of S_{n} in order. Otherwise, we have |S_{n}| = L − 2n + 1. If m is even, L − 2n + 1 = m and we again obtain a minimum coprime labeling for P_{m} + P_{n}. If m is odd, L − 2n + 1 = m − 1, and we are short of one label. We resolve this by recalling that there exists some q_{ℓ} ≢ 1, 10 (mod 11). To construct S_{n}, we have deleted one of q_{i} − 1, q_{i} + 1 for each q_{i}; hence there is some x = q_{ℓ} ± 1, 11 ∤ x that does not appear in S_{n}. As q_{1} > 23, we may label the vertices of P_{m} with the sequence

x, 11, 12, 5, 4, 3, 8, 7, 6, 13, 10, 9, 14,

followed by all of the elements x ∈ S_{n} such that 15 ≤ x ≤ L, followed by 2. This yields a minimum coprime labeling for P_{m} + P_{n}.

The condition M ≥ R_{N−1} −2N +1 in Theorem 6 is sufficient but certainly not necessary; by Theorem 4, it is known, for instance, that if N = 3 or 4, it suffices to set M ≥ N. The following theorem extends this result to N = 5.

Theorem 15. For m ≥ 5, the minimum coprime number of P_{m} + P_{5} is

𝔭𝔯(P_{m} + P_{5}) = \begin{cases}m + 8, & if m is odd; \\ m + 9, & if m is even. \end{cases}

Proof. We prove the theorem for each case as follows.

• If m ≥ 20, we are done by Theorem 6 as R_{4} = 29.

• If m = 5, we may label the vertices of the first path with the sequence 1, 3, 5, 9, 13, and the vertices of the second path with 2, 7, 4, 11, 8.

• If 6 ≤ m ≤ 10, we may label the vertices of P_{5} with the sequence 3, 5, 9, 1, 15, and the vertices of P_{m} with the first m integers in the sequence

2, 7, 4, 11, 8, 13, 14, 17, 16, 19.

• If 11 ≤ m ≤ 17, we may label the vertices of P_{5} with the sequence 1, 11, 13, 17, 19, and the vertices of P_{m} with the first m integers in the sequence

2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 16, 21, 10, 23, 12, 25, 24.

• If m = 18 or 19, we may label the vertices of P_{5} with the sequence 1, 13, 17, 19, 23, and the vertices of P_{m} with the first m integers in the sequence

2, 3, 4, 5, 6, 7, 26, 9, 10, 11, 14, 15, 16, 21, 22, 25, 8, 27, 20.

Our work on the join of two paths also offers insight on the complete bipartite graphs. Fu and Huang [14] proved that, for m ≤ n, K_{m,n} is prime if and only if m ≤ π(m+n)−π(\frac{m+n}{2})+1. Seoud, Diab, and Elsakhawi [27] showed that K_{2,n} is prime for all n and that K_{3,n} is prime unless n = 3, 7. Berliner et al. [5] provide all values of n for m ≤ 13 for which K_{m,n} is prime and note that K_{m,n} is prime for all n ≥ R_{m−1} − m, as implied by [14]. They also ask about the behavior of 𝔭𝔯(K_{m,n}) when n < R_{m−1} − m. By Proposition 9, Theorem 6 immediately implies the following bound on 𝔭𝔯(K_{m,n}), which provides a partial answer to this question.

Corollary 16. If n ≥ R_{m−1} − 2m + 1, then

𝔭𝔯(K_{m,n}) ≤ 2 ⌈\frac{n − 1}{2}⌉ + 2m − 1.

In fact, a slight modification of the first part of the proof of Theorem 6 enables us to show that, more generally,

Theorem 17. If m ≤ n ≤ R_{m−1} − m, then 𝔭𝔯(K_{m,n}) ≤ R_{m−1}.

Proof. We label the vertices of \overline{K}_{m} with 1 and the m − 1 largest primes up to R_{m−1}, which are, in particular, at least ⌈\frac{R_{m−1}}{2} ⌉. Hence they are each coprime to all of the other integers

up to R_{m−1}. We may use any n of the remaining integers to label the vertices of \overline{K}_{n}.

However, we note that for N ≥ 6, it is in general not sufficient to take M ≥ N.

Remark 18. There exist positive integers m ≥ n such that

𝔭𝔯(P_{m} + P_{n}) > 2 ⌈\frac{m − 1}{2}⌉ + 2n − 1.

We now present a number of examples and counterexamples for Remark 18 that illustrate the complexity of the behavior of 𝔭𝔯(P_{m} + P_{n}) for n ≤ m ≤ R_{n−1} − 2n.

Example 19 (n = 6). • For 6 ≤ m ≤ 9, we have

𝔭𝔯(P_{m} + P_{6}) = \begin{cases}m + 10, & if m is odd; \\ m + 11, & if m is even. \end{cases}

This follows from labeling the vertices of P_{6} with the sequence 3, 5, 9, 1, 15, 11 and the vertices of P_{m} with the first m integers in the sequence

2, 7, 4, 17, 8, 13, 14, 19, 16.

• For m = 10 or 11, this equality does not hold. We prove this by contradiction: if 𝔭𝔯(P_{10}+P_{6}) = 𝔭𝔯(P_{11}+P_{6}) = 21, then there exist minimum coprime labelings of P_{10}+P_{6} and P_{11} + P_{6} using 5 or 6 even integers respectively and each of the odd integers up to 21. The vertices of P_{6} must be labeled with the set of integers S = {3, 5, 7, 9, 15, 21}, as no subset of S is pairwise coprime to its complement in S. Thus all of the integers in S must be used as labels for the same path, and there are too many odds in S to be used as labels in P_{10} or P_{11}. However, because S contains a total of 6 integers, 4 of which are multiples of 3, it is not possible to arrange the elements of S in a sequence such that adjacent elements are coprime. Therefore 𝔭𝔯(P_{m}+P_{6}) > 21 for m = 10 or 11. The same reasoning shows that the minimum coprime numbers of P_{10} + P_{6} and P_{11} + P_{6} exceeds 22. In fact, we may construct labelings to show that 𝔭𝔯(P_{10} + P_{6}) = 𝔭𝔯(P_{11} + P_{6}) = 23.

Example 20 (n = 7).

• For m = 7, we have 𝔭𝔯(P_{7} + P_{7}) = 19. This follows from labeling the vertices of one copy of P_{7} with the sequence 3, 5, 9, 1, 15, 11, 13, and the vertices of the second copy with the sequence 2, 7, 4, 17, 8, 19, 16.

• For m = 8 or 10, we have 𝔭𝔯(P_{m} + P_{7}) = m + 13. This follows from labeling the vertices of P_{7} with the sequence 3, 5, 9, 7, 15, 1, 21, and the vertices of P_{m} with the first m integers in the sequence

2, 11, 4, 13, 8, 17, 16, 19, 22, 23.

• For m = 9, the lower bound is not tight. As in Example 19, we prove this by contradiction. If 𝔭𝔯(P_{9} + P_{7}) = 21, then there would exist a minimum coprime labeling of P_{9} + P_{7} using 5 of the even integers and all of the odd integers up to 21. In particular, all the integers in the set S = {3, 5, 7, 9, 15, 21} must be used as labels for the vertices of P_{7}, by the same reasoning as before. However, there are fewer than 5 even integers up to 21 that are coprime to all of the elements in S. We can construct a coprime labeling to show that 𝔭𝔯(P_{9} + P_{7}) = 22. This case demonstrates that the minimum coprime number of the join of certain paths is constrained by the even integers rather than the odds; it is also interesting that the lower bound may be tight for both m − 1 and m + 1 but fail to be tight for m.

Our methods in Theorem 6 also enable us to prove the following results on the joins of cycles and paths.

Theorem 21. For any positive integer N, if M ≥ R_{N−1} − 2N + 1, then for all m ≥ M and n ≤ N, the minimum coprime number of C_{m} + C_{n} is

𝔭𝔯(C_{m} + C_{n}) = \begin{cases}m + 2n, & if m is odd; \\ m + 2n − 1, & if m is even. \end{cases}

Proof. Label the vertices of P_{m} + P_{n} as in the proof of Theorem 6. Then the labels for P_{n} are all either 1 or prime, so in particular the endpoints of P_{n} have coprime labels and we may join them to form C_{n} without violating the coprime labeling condition. If m is even, then one endpoint of P_{m} is labeled with 2 and the other is labeled with an odd integer, so we may also join the endpoints of P_{m} to form C_{m} without violating the coprime labeling condition, obtaining a coprime labeling of C_{m} + C_{n}. This labeling is a minimum coprime labeling because we have 𝔭𝔯(C_{m} + C_{n}) ≥ 𝔭𝔯(P_{m} + P_{n}) by Proposition 9.

If m is odd, then 𝔭𝔯(C_{m} + C_{n}) ≥ m + 2n by Proposition 11, as α(C_{m} + C_{n}) = ⌊\frac{m}{2}⌋. Recall that the ordered list S_{n} contains either m or m − 1 elements. If |S_{n}| = m − 1, the last element of S_{n} is L = m + 2n − 2. Labeling the vertices of P_{m} with the sequence S_{n} with m + 2n appended and joining the endpoints of P_{m} to form C_{m} therefore yields a minimum coprime labeling for C_{m} + C_{n}. If |S_{n}| = m, then p_{n−1} = L = m + 2n − 2. We may assume that n ≥ 5 as the other cases are known by [4]; therefore p_{1} > 17. We consider the following cases.

• If m + 2n − 4 is composite, the last two elements of S_{n} are m + 2n − 4 and m + 2n − 3. Labeling the vertices of P_{m} with the sequence S_{n}, replacing m + 2n − 3 by m + 2n, and joining the endpoints of P_{m} to form C_{m} therefore yields a minimum coprime labeling for C_{m} + C_{n}, as we have gcd(m + 2n − 4, m + 2n) = gcd(m + 2n, 2) = 1.

• If m + 2n − 4 is prime, the last two elements of S_{n} are m + 2n − 6 and m + 2n − 5. If 3 ∤ m + 2n, we may replace m + 2n − 5 with m + 2n to obtain a minimum coprime labeling for C_{m} + C_{n}, as above. If 3 | m + 2n, we join the endpoints of P_{m} to form C_{m}, replace m + 2n − 5 with m + 2n, and rearrange the labels surrounding the endpoints to read

…, m + 2n − 6, 2, m + 2n, 4, 3, 5, 6, ….

The proof of Theorem 21 immediately implies the following two corollaries on the join of a cycle and a path.

Corollary 22. For any positive integer N, if M ≥ R_{N−1} − 2N + 1, then for all m ≥ M and n ≤ N, the minimum coprime number of C_{m} + P_{n} is

𝔭𝔯(C_{m} + P_{n}) = \begin{cases}m + 2n, & if m is odd; \\ m + 2n − 1, & if m is even. \end{cases}

Corollary 23. For any positive integer N, if M ≥ R_{N−1} − 2N + 1, then for all m ≥ M and n ≤ N, the minimum coprime number of P_{m} + C_{n} is

𝔭𝔯(P_{m} + C_{n}) = \begin{cases}m + 2n − 2, & if m is odd; \\ m + 2n − 1, & if m is even. \end{cases}

5 Minimum coprime number of a random subgraph

In this section, we prove Theorem 7.

Lemma 24. Denote n := |V (G)|. If n is sufficiently large and α(G) < \sqrt{n}, then 𝔭𝔯(G) ≥ p_{n−α(G)⌊\sqrt{n}⌋}.

Proof. Assume that we have a minimum coprime labeling of G. For any prime p, the vertices with labels which are multiples of p must form an independent set. Thus as we let p range over p_{1}, …, p_{⌊\sqrt{n}⌋} respectively, we obtain ⌊\sqrt{n}⌋ (possibly non-disjoint) independent sets, each of which contains at most α(G) vertices. Hence there are at least n − α(G)⌊\sqrt{n}⌋ vertices whose labels are not multiples of any prime up to p_{⌊\sqrt{n}⌋}. If any of the remaining labels exceeds p_{n}, then we are done. Otherwise, as the remaining labels only have prime factors larger than p_{⌊\sqrt{n}⌋} and p_{⌊\sqrt{n}⌋}^{2} > p_{n} for large n, the remaining labels must all be prime. Using the next n − α(G)⌊\sqrt{n}⌋ primes after p_{⌊\sqrt{n}⌋} as labels yields the desired result.

Proof of Theorem 7. By a celebrated result of Bollobás and Erdős [6], we have ω(G(n, p)) ∼ 2 log_{1/p} n almost surely, where ω(G) denotes the clique number of G, i.e., the size of the largest complete subgraph of G. As α(G(n, p)) = ω(G(n, 1 − p)), by the prime number theorem, p_{n−α(G)⌊\sqrt{n}⌋} ∼ n log n, and using Lemma 24, we have 𝔭𝔯(G(n, p)) ∼ n log n almost surely as n → ∞.

6 Further directions

Here we pose a number of open questions in coprime graph labeling. Question 25. We observed in Examples 19 and 20 that 𝔭𝔯(P_{m} + P_{n}) exhibits interesting behavior when n ≤ m ≤ R_{n−1} − 2n. Is there a nice characterization of 𝔭𝔯(P_{m} + P_{n}) in these cases, and in particular, is it possible to predict when 𝔭𝔯(P_{m} + P_{n}) = 2 ⌈\frac{m−1}{2}⌉ + 2n − 1? Question 26. Is it sufficient to take M ≥ N in Theorem 6 for sufficiently large N? This is conjectured in [4]. Question 27. Can we improve on the bounds for 𝔭𝔯(K_{m,n}) in Theorem 17? In particular, can we obtain sharper bounds on 𝔭𝔯(K_{n,n})? (The first few values of 𝔭𝔯(K_{n,n}) are given in sequence \underline{A213273} in the OEIS [30].) Question 28. The Cartesian product P_{m}□P_{n} is called a grid graph. In particular, if m = 2, the graph P_{2}□P_{n} is called a ladder. Dean [7] and Ghorbani and Kamali [16] showed independently that all ladders are prime, resolving a conjecture of Varkey. Other grid graphs have been shown to be prime, including P_{m}□P_{n} if m ≤ n and n is prime [31], and a few other cases in [18]. It it true that P_{m}□P_{n} is prime for all m and n? This would settle a conjecture in [31]. Question 29. There has been a substantial amount of research conducted on the clique number and independence number of a random subgraph. Would any of these results enable us to obtain lower bounds on 𝔭𝔯(G_{p}) for arbitrary G? Question 30. For arbitrary G, the trivial upper bound 𝔭𝔯(G_{p}) ≤ 𝔭𝔯(G) is asymptotically tight, as we may observe in the case where G is prime. Is it possible to obtain a better upper bound on 𝔭𝔯(G_{p}) for specific classes of G?

7 Acknowledgments

This research was conducted at the University of Minnesota, Duluth REU and was supported by NSF/DMS grant 1659047 and NSA grant H98230-18-1-0010. The author would like to thank Joe Gallian for suggesting this problem, and Aaron Berger and Pat Devlin for numerous helpful conversations.

References

[1] R. Ahlswede and L. H. Khachatrian, On extremal sets without coprimes, Acta Arith. 66 (1994), 89–99.

[2] R. Ahlswede and L. H. Khachatrian, Maximal sets of numbers not containing k + 1 pairwise coprime integers, Acta Arith. 72 (1995), 77–100.

[3] R. Ahlswede and L. H. Khachatrian, Sets of integers and quasi-integers with pairwise common divisor, Acta Arith. 74 (1996), 141–153.

[4] John Asplund and N. Bradley Fox, Minimum coprime labelings for operations on graphs, Integers 19 (2019), Article A24.

[5] A. H. Berliner, N. Dean, J. Hook, A. Mbirika, and C. D. McBee, Coprime and prime labelings of graphs, J. Integer Seq. 19 (2016), Article 16.5.8.

[6] B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Phil. Soc. 80 (1976), 419–427.

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

[8] Paul Erdős, Remarks in number theory IV, Mat. Lapok 13 (1962), 228–255.

[9] Paul Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89–115.

[10] Paul Erdős and A. Sárközy, On sets of coprime integers in intervals, Hardy-Ramanujan J. 16 (1993), 1–20.

[11] Paul Erdős, A. Sárközy, and E. Szemerédi, On some extremal properties of sequences of integers, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 12 (1969), 131–135.

[12] Paul Erdős, A. Sárközy, and E. Szemerédi, On some extremal properties of sequences of integers II, Publ. Math. Debrecen 27 (1980), 117–125.

[13] Paul Erdős and G. N. Sárközy, On cycles in the coprime graph of integers, Electron. J. Combin. 4 (1997), Article R8.

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

[15] Joseph A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2018), Article DS6.

[16] E. Ghorbani and S. Kamali, Prime labeling of ladders, preprint, 2016. Available at

    https://arxiv.org/abs/1610.08849.

[17] P. Haxell, O. Pikhurko, and A. Taraz, Primality of trees, J. Comb. 2 (2011), 481–500.

[18] A. Kanetkar, Prime labeling of grids, AKCE J. Graphs Comb. 6 (2009), 135–142.

[19] H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119– 134.

[20] O. Pikhurko, Trees are almost prime, Discrete Math. 307 (2007), 1455–1462.

[21] C. Pomerance and A. Sárközy, Combinatorial number theory. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics. MIT Press, 1995.

[22] C. Pomerance and J. L. Selfridge, Proof of D. J. Newman’s coprime mapping conjecture, Mathematika 27 (1980), 69–83.

[23] S. Ramanujan, A proof of Bertrand’s postulate, J. Indian Math. Soc. 11 (1919), 181– 182.

[24] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94.

[25] H. Salmasian, A result on prime labelings of trees, Bull. Inst. Combin. Appl. 28 (2000), 36–38.

[26] G. N. Sárközy, Complete tripartite subgraphs in the coprime graph of integers, Discrete Math. 202 (1999), 227–238.

[27] M. A. Seoud, A. T. Diab, and E. A. Elsakhawi, On strongly-c harmonious, relatively prime, odd graceful and cordial graphs, Proc. Math. Phys. Soc. Egypt 73 (1998), 33–55.

[28] M. A. Seoud, A. El Sonbaty, and A. E. A. Mahran, Primality of some graphs, Ars Combin. 112 (2013), 459–469.

[29] M. A. Seoud and M. Z. Youssef, On prime labeling of graphs, Congr. Numer. 141 (1999), 203–215.

[30] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, 2020. Available at

    https://oeis.org.

[31] M. Sundaram, R. Ponraj, and S. Somasundaram, On a prime labeling conjecure, Ars Combin. 80 (2006), 205–209.

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

[33] M. Z. Youssef and E. A. Elsakhawi, Some properties of prime graphs, Ars Combin. 84 (2007), 129–140.

2010 Mathematics Subject Classification: Primary 05C78; Secondary 05C80, 11A05. Keywords: coprime labeling, prime labeling, prime graph, Ramanujan prime, random graph.

(Concerned with sequences \underline{A104272} and \underline{A213273}.)

Received July 15 2020; revised versions received October 19 2020; November 29 2020. Published in Journal of Integer Sequences, December 2 2020.

Return to Journal of Integer Sequences home page.