Coprime Index of a Graph

Let G=(V,E) be a graph. An injection f:V→{2,3,4,…,} is called a coprime labeling of G if for any two vertices u,v∈V, u and v are adjacent if and only if f(u) and f(v) are coprime. We prove that every graph admits a coprime labeling. A prime number p is said to be used by the coprime labeling f if p divides f(v) for some v∈V. Let μ(G,f) be the number of primes used by the labeling f. Then min⁡{μ(G,f):f is a coprime labeling of G} is called the coprime index of G and is denoted by μ(G). We prove that for any graph G with Δ(G)