A graph \(G\) with vertex set \(V(G)\) and edge set \(E(G)\) is said to have an odd prime labeling if there exists a bijection \(f:V(G)\to \{1,3,5,\dots,2n-1\}\), where \(n=|V(G)|\), such that \(\gcd(f(x),f(y))=1\) for every edge \(xy\in E(G)\). In this paper, we study odd prime labelings of graphs arising from duplication operations on graph elements. We obtain several results for graphs derived from the path graph \(P_n\), the cycle graph \(C_n\), and the star graph \(K_{1,n}\) under various vertex- and edge-duplication constructions.
Let \(G=(V,E)\) be a finite, undirected graph with vertex set \(V(G)\) and edge set \(E(G)\). In graph theory, odd prime labeling has emerged as an important area of study, where vertices are assigned distinct odd integers such that adjacent vertices have relatively prime labels. This work presents the preservation of odd prime labeling under duplication operations for three fundamental graph classes, namely \(P_n\), \(C_n\), and \(K_{1,n}\).
Our notation follows standard conventions: \(|V(G)|\) denotes the number of vertices of the graph, \(|E(G)|\) denotes the number of edges of the graph, and all graphs considered are simple and non-trivial. The graph-theoretic terminology follows Bondy [1], while the number-theoretic foundations follow Burton [2].
Definition 1.1. Let \(G\) be a graph with vertex set \(V(G)\) and \(n\) vertices. We say that \(G\) has an odd prime labeling if there exists a bijective function \[f:V(G)\rightarrow \{1,3,5,\dots,2n-1\}\] such that, for every edge \(xy\in E(G)\), the integers \(f(x)\) and \(f(y)\) are relatively prime.
Consider a finite, undirected graph \(G=(V,E)\), where \(V\) represents the vertex set and \(E\) denotes the edge set. In graph theory, the components of \(V\) and \(E\) are collectively referred to as graph elements. In this study, we adopt the following notation:
\(C_n\) denotes a cycle graph with \(n\) vertices;
\(P_n\) denotes a path graph consisting of \(n\) vertices; and
\(K_{1,n}\) denotes a star graph with one apex vertex of degree \(n\) and \(n\) pendant vertices, each of degree one.
Global convention. Throughout this section, for any graph \(G\), we write \[N=|V(G)|.\]
A graph \(G\) is said to be an odd prime graph if there exists a bijection \[f:V(G)\to \{1,3,5,\ldots,2N-1\},\] such that \[\gcd\bigl(f(u),f(v)\bigr)=1 \qquad \text{for every } uv\in E(G).\]
Hence, whenever a graph is obtained from a known family by duplication of a vertex or an edge, the labeling must always be defined with respect to the order \(N\) of the new graph.
Definition 2.1. Duplication of a vertex \(v\) of a graph \(G\) produces a new graph \(G^{\prime}\) by adding a new vertex \(v^{\prime}\) such that \(N(v^{\prime})=N(v)\). In other words, a vertex \(v^{\prime}\) is said to be a duplication of \(v\) if all the vertices adjacent to \(v\) in \(G\) are also adjacent to \(v^{\prime}\) in \(G^{\prime}\).
Definition 2.2. Duplication of a vertex \(v_{k}\) by a new edge \(e=v^{\prime}_{k}v^{\prime\prime}_{k}\) in a graph \(G\) produces a new graph \(G^{\prime}\) such that \[N(v^{\prime}_{k})=\{v_{k},v^{\prime\prime}_{k}\} \quad \text{and} \quad N(v^{\prime\prime}_{k})=\{v_{k},v^{\prime}_{k}\}.\]
Definition 2.3. Duplication of an edge \(e=uv\) by a new vertex \(w\) in a graph \(G\) produces a new graph \(G^{\prime}\) such that \[N(w)=\{u,v\}.\]
Definition 2.4. Duplication of an edge \(e=uv\) of a graph \(G\) produces a new graph \(G^{\prime}\) by adding an edge \(e^{\prime}=u^{\prime}v^{\prime}\) such that \[N(u^{\prime})=N(u)\cup\{v^{\prime}\}-\{v\} \quad \text{and} \quad N(v^{\prime})=N(v)\cup\{u^{\prime}\}-\{u\}.\]
Postulate 2.5(Bertrand’s Postulate).For any integer \(n>1\), there exists a prime \(p\) such that \[n<p<2n.\]
Lemma 2.6. For any \(a\geq 1\) and any \(i\geq 1\), the integers \(1+a(i-1)\) and \(1+ai\) are relatively prime.
Proof. We have \[\gcd(1+a(i-1),1+ai)=\gcd(1+a(i-1),a).\] Since \[1+a(i-1)-(i-1)a=1,\] it follows that \(\gcd(1+a(i-1),a)=1\). Therefore, \(1+a(i-1)\) and \(1+ai\) are relatively prime. ◻
Lemma 2.7. For any integers \(a\) and \(b\), \[\gcd(a,b)=\gcd(a,b-a).\]
Proof. Let \(d=\gcd(a,b)\). Then \(d\mid a\) and \(d\mid b\). Since \(d\mid b\) and \(d\mid a\), it follows that \(d\mid (b-a)\). Thus, \(d\) is a common divisor of \(a\) and \(b-a\). Hence, \[d\leq \gcd(a,b-a).\]
Now let \(d'=\gcd(a,b-a)\). Then \(d'\mid a\) and \(d'\mid (b-a)\). Since \(d'\mid a\) and \(d'\mid (b-a)\), we have \(d'\mid (b-a)+a=b\). Thus, \(d'\) is a common divisor of \(a\) and \(b\). Hence, \[d'\leq \gcd(a,b)=d.\] From \(d\leq d'\) and \(d'\leq d\), we conclude that \(d=d'\). Therefore, \[\gcd(a,b)=\gcd(a,b-a).\] ◻
Theorem 2.8. \(P_n\) is an odd prime graph for every \(n\geq 1\).
Proof. Let \[V(P_n)=\{v_1,v_2,\ldots,v_n\}\] and \[E(P_n)=\{v_iv_{i+1}:1\le i\le n-1\}.\] Then \(|V(P_n)|=n=N\). Hence the required codomain is \[\{1,3,5,\ldots,2N-1\}.\] Define \[f:V(P_n)\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_i)=2i-1,\qquad 1\le i\le n.\]
We now show that \(f\) is bijective. The labels assigned by \(f\) are exactly \[1,3,5,\ldots,2n-1=\{1,3,5,\ldots,2N-1\},\] and they are all distinct. Hence \(f\) is injective. Since both \(V(P_n)\) and the codomain \(\{1,3,5,\ldots,2N-1\}\) have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(P_n\). For each edge \(v_iv_{i+1}\in E(P_n)\), where \(1\le i\le n-1\), we have \[\begin{aligned} \gcd(f(v_i),f(v_{i+1})) &=\gcd(2i-1,2i+1),\qquad 1\leq i \leq n-1 \nonumber\\ &=\gcd(2i-1,(2i+1)-(2i-1)) \nonumber\\ &=\gcd(2i-1,2)=1. \nonumber \end{aligned}\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(P_n\). Hence \(f\) is an odd prime labeling of \(P_n\), and so \(P_n\) is an odd prime graph. ◻
Theorem 2.9. The graph obtained by duplication of a vertex in \(P_n\) is an odd prime graph.
Proof. The result holds for \(n=1,2\) by direct verification. Therefore, we assume that \(n\geq3\). Let \(v_1,v_2,\dots,v_n\) be the consecutive vertices of \(P_n\), and let \(G\) be the graph obtained by duplication of the vertex \(v_j\) by a new vertex \(v_j'\). Then \(G\) has \(N=n+1\) vertices. Depending on \(\deg(v_j)\), we consider the following cases.
Case (i). If \(\deg(v_j)=1\), then \(v_j\) is either \(v_1\) or \(v_n\). Without loss of generality, let \(v_j=v_1\). Define \[f:V(G)\rightarrow \{1,3,5,\dots,2N-1\}\] by \[f(v_i)=2i-3,\quad 2\leq i\leq n,\qquad f(v_1)=2n-1,\qquad f(v_1')=2n+1.\]
Since the assigned labels are distinct and since \(|V(G)|=N\) while the set \(\{1,3,5,\ldots,2N-1\}\) contains exactly \(N\) elements, \(f\) is bijective. Also, we have \[\begin{aligned} \gcd(f(v_i),f(v_{i+1})) &=\gcd(2i-3,2i-1)=\gcd(2i-3,2)=1, \quad 2\leq i\leq n-1, \nonumber\\ \gcd(f(v_2),f(v_1')) &=\gcd(1,2n+1)=1, \nonumber\\ \gcd(f(v_2),f(v_1)) &=\gcd(1,2n-1)=1. \nonumber \end{aligned}\]
Hence \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Thus, \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph.
Case (ii). If \(\deg(v_j)\neq1\), then \(j\in\{2,3,\dots,n-1\}\). Define \[f:V(G)\rightarrow \{1,3,5,\dots,2N-1\}\] by \[f(v_j)=5,\qquad f(v_{j-1})=7,\qquad f(v_{j+1})=1,\qquad f(v_j')=3,\] \[f(v_i)=2j-2i+5,\qquad 1\leq i\leq j-2,\] and \[f(v_i)=2i+1,\qquad j+2\leq i\leq n.\]
We now show that \(f\) is injective. The vertices \(v_{j+1},v_j',v_j,\) and \(v_{j-1}\) receive the distinct labels \(1,3,5,\) and \(7\), respectively. Also, for \(i=1,2,\dots,j-2\), the labels \(f(v_i)=2j-2i+5\) form the distinct odd integers \[9,11,\dots,2j+3,\] while for \(i=j+2,j+3,\dots,n\), the labels \(f(v_i)=2i+1\) form the distinct odd integers \[2j+5,2j+7,\dots,2n+1.\] These labels are all distinct, and therefore \(f\) is injective. Since the domain and codomain have the same cardinality \(N\), the function \(f\) is bijective.
Also, we have \[\begin{aligned} \gcd(f(v_j),f(v_{j+1}))&=\gcd(5,1)=1, \nonumber\\ \gcd(f(v_j),f(v_{j-1}))&=\gcd(5,7)=1, \nonumber\\ \gcd(f(v_j'),f(v_{j+1}))&=\gcd(3,1)=1, \nonumber\\ \gcd(f(v_j'),f(v_{j-1}))&=\gcd(3,7)=1, \nonumber\\ \gcd(f(v_{j+1}),f(v_{j+2}))&=\gcd(1,f(v_{j+2}))=1, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2j-2i+5,2j-2i+3) \notag\\ &=\gcd(2j-2i+5,2)=1,\qquad 1\leq i\leq j-2, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2i+1,2i+3)=\gcd(2i+1,2)=1,\qquad j+2\leq i\leq n-1. \nonumber \end{aligned}\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Thus, \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph in this case as well. ◻
Theorem 2.10. The graph obtained by duplication of a vertex by an edge in \(P_n\) is an odd prime graph.
Proof. If a vertex of \(P_n\) is duplicated by an edge, then the new graph has \(N=n+2\) vertices. We assume that \(n\geq3\), since the result is obvious for \(n=1,2\). Let \(v_1,v_2,\dots,v_n\) be the consecutive vertices of \(P_n\), and let \(G\) be the graph obtained by duplication of a vertex \(v_j\) by an edge \(v_j'v_j''\). Define \[f:V(G)\rightarrow \{1,3,5,\dots,2N-1\}\] by \[f(v_j)=1,\qquad f(v_j')=3,\qquad f(v_j'')=5,\] \[f(v_i)=2j-2i+5,\qquad 1\leq i\leq j-1,\] and \[f(v_i)=2i+3,\qquad j+1\leq i\leq n.\]
We show that \(f\) is injective. The vertices \(v_j\), \(v_j'\), and \(v_j''\) receive the distinct labels \(1,3,\) and \(5\), respectively. Moreover, for \(i=1,2,\dots,j-1\), the labels \(f(v_i)=2j-2i+5\) form the distinct odd integers \[7,9,11,\dots,2j+3,\] while for \(i=j+1,j+2,\dots,n\), the labels \(f(v_i)=2i+3\) form the distinct odd integers \[2j+5,2j+7,\dots,2n+3.\] These three sets of labels are pairwise disjoint. Hence no two vertices of \(G\) receive the same label, and therefore \(f\) is injective. Since \(|V(G)|=N\) and the set \(\{1,3,5,\ldots,2N-1\}\) contains exactly \(N\) elements, it follows that \(f\) is bijective.
Also, we have \[\begin{aligned} \gcd(f(v_j),f(v_j'))&=\gcd(1,3)=1, \nonumber\\ \gcd(f(v_j),f(v_j''))&=\gcd(1,5)=1, \nonumber\\ \gcd(f(v_j'),f(v_j''))&=\gcd(3,5)=1, \nonumber\\ \gcd(f(v_j),f(v_{j+1}))&=\gcd(1,f(v_{j+1}))=1, \nonumber\\ \gcd(f(v_j),f(v_{j-1}))&=\gcd(1,f(v_{j-1}))=1,\qquad&& j\geq2, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2j-2i+5,2j-2i+3) \notag\\ &=\gcd(2j-2i+5,2)=1,\qquad&& 1\leq i\leq j-2, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2i+3,2i+5) \notag\\ &=\gcd(2i+3,2)=1,\qquad &&j+1\leq i\leq n-1. \nonumber \end{aligned}\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Thus, \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.11. The graph obtained by duplication of every vertex by an edge in \(P_n\) is an odd prime graph.
Proof. We assume that \(n\geq3\), since the result is obvious for \(n=1,2\). Let \(v_1,v_2,\dots,v_n\) be the consecutive vertices of \(P_n\), and let \(G\) be the graph obtained by duplication of every vertex \(v_i\) by an edge \(v_i'v_i''\), for \(i=1,2,\dots,n\). Then \(G\) is a graph with \(N=3n\) vertices and has \(n\) vertex-disjoint cycles, each of length \(3\). Define \[f:V(G)\rightarrow \{1,3,5,\dots,2N-1\}\] by \[\begin{aligned} f(v_i) &= 6i-5, \qquad 1\leq i\leq n,\\ f(v_i') &= 6i-3, \qquad 1\leq i\leq n,\\ f(v_i'') &= 6i-1, \qquad 1\leq i\leq n. \end{aligned}\]
We now show that \(f\) is bijective. The assigned labels are \[f(v_i)=6i-5,\qquad f(v_i')=6i-3,\qquad f(v_i'')=6i-1,\qquad 1\leq i\leq n,\] which are precisely the distinct odd integers \[1,3,5,\dots,6n-1.\] Hence no two vertices of \(G\) receive the same label. Also, \(|V(G)|=3n=N\), and the set \[\{1,3,5,\dots,2N-1\}=\{1,3,5,\dots,6n-1\}\] contains exactly \(N=3n\) elements. Therefore, \(f\) is a bijection.
Furthermore, we have \[\begin{aligned} \gcd(f(v_i),f(v_{i+1})) &=\gcd(6i-5,6i+1)=\gcd(6i-5,6)=1,\qquad 1\leq i\leq n-1, \nonumber\\ \gcd(f(v_i),f(v_i')) &=\gcd(6i-5,6i-3)=\gcd(6i-5,2)=1,\qquad 1\leq i\leq n, \nonumber\\ \gcd(f(v_i),f(v_i'')) &=\gcd(6i-5,6i-1)=\gcd(6i-5,4)=1,\qquad 1\leq i\leq n, \nonumber\\ \gcd(f(v_i'),f(v_i'')) &=\gcd(6i-3,6i-1)=\gcd(6i-3,2)=1,\qquad 1\leq i\leq n. \nonumber \end{aligned}\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Thus, \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.12. The graph obtained by duplication of an edge by a vertex in \(P_n\) is an odd prime graph.
Proof. We assume that \(n\geq3\), since the result is obvious for \(n=1,2\). Let \(v_1,v_2,\dots,v_n\) be the consecutive vertices of \(P_n\), and let \(G\) be the graph obtained by duplication of an edge \(v_jv_{j+1}\) by a vertex \(v_j'\). Then the new graph has \(N=n+1\) vertices. Define \[f:V(G)\rightarrow \{1,3,5,\dots,2N-1\}\] by \[f(v_j)=1,\qquad f(v_j')=3,\] \[f(v_i)=2i+2n-2j+3,\qquad 1\leq i\leq j-1,\] and \[f(v_i)=2i-2j+3,\qquad j+1\leq i\leq n.\] We now show that \(f\) is bijective. First, \(f(v_j)=1\) and \(f(v_j')=3\). Next, for \(i=j+1,j+2,\dots,n\), the labels \(f(v_i)=2i-2j+3\) are precisely the distinct odd integers \[5,7,9,\dots,2n-2j+3.\] Also, for \(i=1,2,\dots,j-1\), the labels \(f(v_i)=2i+2n-2j+3\) are precisely the distinct odd integers \[2n-2j+5,\,2n-2j+7,\dots,2n+1.\] Hence the labels assigned by \(f\) are exactly \[1,3,5,7,\dots,2n+1=\{1,3,5,\dots,2N-1\},\] and all of them are distinct. Therefore \(f\) is injective. Since \(|V(G)|=N=n+1\) and the codomain \(\{1,3,5,\dots,2N-1\}\) also contains exactly \(N\) elements, it follows that \(f\) is bijective.
Also, we have \[\begin{aligned} \gcd(f(v_j),f(v_{j+1}))&=\gcd(1,f(v_{j+1}))=1, \nonumber\\ \gcd(f(v_j),f(v_{j-1}))&=\gcd(1,f(v_{j-1}))=1,\qquad j\geq2, \nonumber\\ \gcd(f(v_j),f(v_j'))&=\gcd(1,3)=1, \nonumber\\ \gcd(f(v_{j+1}),f(v_j'))&=\gcd(5,3)=1, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2i+2n-2j+3,2i+2n-2j+1) \nonumber\\ &=\gcd(2i+2n-2j+3,2)=1,\qquad 1\leq i\leq j-2, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2i-2j+3,2i-2j+1) \nonumber\\ &=\gcd(2i-2j+3,2)=1,\qquad j+1\leq i\leq n-1. \nonumber \end{aligned}\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Thus, \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.13. The graph obtained by duplication of an edge in \(P_n\) is an odd prime graph.
Proof. We assume that \(n\geq4\), since the result is obvious for \(n=1,2,3\). Let \(v_1,v_2,\dots,v_n\) be the consecutive vertices of \(P_n\), and let \(G\) be the graph obtained by duplication of an edge \(e=v_jv_{j+1}\) by an edge \(e'=v_j'v_{j+1}'\) in \(P_n\). Then the new graph has \(N=n+2\) vertices. We consider the following two cases.
Case (i). Let \(G\) be the graph obtained by duplication of an edge \(e=v_jv_{j+1}\) by an edge \(v_j'v_{j+1}'\) in \(P_n\). Then \(G\) contains the cycle \[C_6=v_{j+2}v_{j+1}'v_j'v_{j-1}v_jv_{j+1}v_{j+2}.\] The vertices \[v_{j+2},\ v_{j+1}',\ v_j',\ v_{j-1},\ v_j,\ v_{j+1}\] can be labeled as \[1,\ 3,\ 5,\ 11,\ 9,\ 7,\] respectively. Consequently, this \(C_6\) is an odd prime graph. Define \[f:V(G)\rightarrow \{1,3,\dots,2N-1\}\] by \[f(v_{j+2})=1,\quad f(v_{j+1}')=3,\quad f(v_j')=5,\quad f(v_{j+1})=7,\quad f(v_j)=9,\quad f(v_{j-1})=11,\] \[f(v_i)=2j-2i+9,\qquad 1\leq i\leq j-2,\] and \[f(v_i)=2i+3,\qquad j+3\leq i\leq n.\]
We now show that \(f\) is bijective in Case (i). The six special vertices receive the distinct labels \(1,3,5,7,9,11\). For \(i=1,2,\dots,j-2\), the labels \(f(v_i)=2j-2i+9\) are precisely the distinct odd integers \[13,15,\dots,2j+7.\] For \(i=j+3,j+4,\dots,n\), the labels \(f(v_i)=2i+3\) are precisely the distinct odd integers \[2j+9,2j+11,\dots,2n+3.\] Hence the labels assigned by \(f\) are exactly \[1,3,5,\dots,2n+3=\{1,3,5,\dots,2N-1\},\] and all of them are distinct. Therefore \(f\) is injective. Since \(|V(G)|=N=n+2\) and the codomain \(\{1,3,5,\dots,2N-1\}\) also contains exactly \(N\) elements, it follows that \(f\) is bijective.
Also, we have \[\begin{aligned} \gcd(f(v_{j-1}),f(v_j'))&=\gcd(11,5)=1, \nonumber\\ \gcd(f(v_{j-1}),f(v_{j-2}))&=\gcd(11,13)=1,\qquad j\geq3, \nonumber\\ \gcd(f(v_{j-1}),f(v_j))&=\gcd(11,9)=1, \nonumber\\ \gcd(f(v_j),f(v_{j+1}))&=\gcd(9,7)=1, \nonumber\\ \gcd(f(v_{j+1}),f(v_{j+2}))&=\gcd(7,1)=1, \nonumber\\ \gcd(f(v_{j+2}),f(v_{j+1}'))&=\gcd(1,3)=1, \nonumber\\ \gcd(f(v_{j+2}),f(v_{j+3}))&=\gcd(1,f(v_{j+3}))=1,\qquad j\leq n-3, \nonumber\\ \gcd(f(v_j'),f(v_{j+1}'))&=\gcd(5,3)=1, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2j-2i+9,2j-2i+7) \nonumber\\ &=\gcd(2j-2i+9,2)=1,\qquad 1\leq i\leq j-3, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2i+3,2i+5) \nonumber\\ &=\gcd(2i+3,2)=1,\qquad j+3\leq i\leq n-1. \nonumber \end{aligned}\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Thus, \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph.
Case (ii). Let \(G\) be the graph obtained by duplication of the edge \(e=v_{n-1}v_n\) by an edge \(v_{n-1}'v_n'\) in \(P_n\). Define \[f:V(G)\rightarrow \{1,3,\dots,2N-1\}\] by \[f(v_n)=5,\qquad f(v_{n-1})=3,\qquad f(v_{n-2})=1,\qquad f(v_n')=9,\qquad f(v_{n-1}')=7,\] and \[f(v_i)=2n-2i+5,\qquad 1\leq i\leq n-3.\]
We now show that \(f\) is bijective. The five special vertices receive the distinct labels \[1,3,5,7,9.\] For \(i=1,2,\dots,n-3\), the labels are precisely the distinct odd integers \[11,13,\dots,2n+3.\] Hence the labels assigned by \(f\) are exactly \[1,3,5,\dots,2n+3=\{1,3,5,\dots,2N-1\},\] and all of them are distinct. Therefore \(f\) is injective. Since \(|V(G)|=N=n+2\) and the codomain \(\{1,3,5,\dots,2N-1\}\) also contains exactly \(N\) elements, it follows that \(f\) is bijective.
Also, we have \[\begin{aligned} \gcd(f(v_{n-2}),f(v_{n-1}))&=\gcd(1,3)=1, \nonumber\\ \gcd(f(v_{n-2}),f(v_{n-3}))&=\gcd(1,f(v_{n-3}))=1, \nonumber\\ \gcd(f(v_{n-2}),f(v_{n-1}'))&=\gcd(1,7)=1, \nonumber\\ \gcd(f(v_{n-1}),f(v_n))&=\gcd(3,5)=1, \nonumber\\ \gcd(f(v_{n-1}'),f(v_n'))&=\gcd(7,9)=1, \nonumber\\ \gcd(f(v_i),f(v_{i+1})) &=\gcd(2n-2i+5,2n-2i+3) \nonumber\\ &=\gcd(2n-2i+5,2)=1,\qquad 1\leq i\leq n-4. \nonumber \end{aligned}\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Thus, \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph in this case as well. ◻
Theorem 2.14. \(K_{1,n}\) is an odd prime graph for every \(n\geq1\).
Proof. Let \[V(K_{1,n})=\{v_0,v_1,\ldots,v_n\}\] and \[E(K_{1,n})=\{v_0v_j:1\leq j\leq n\}.\] Then \(K_{1,n}\) has \(N=n+1\) vertices. Define \[f:V(K_{1,n})\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_i)=2i+1,\qquad 0\leq i\leq n.\]
Since the labels assigned by \(f\) are distinct and since \(|V(K_{1,n})|=N\) while the set \(\{1,3,5,\ldots,2N-1\}\) contains exactly \(N\) elements, \(f\) is bijective. Also, \[\gcd(f(v_0),f(v_i))=\gcd(1,2i+1)=1,\qquad 1\leq i\leq n.\] Thus, \(f\) is an odd prime labeling of \(K_{1,n}\), and consequently \(K_{1,n}\) is an odd prime graph. ◻
Theorem 2.15. The graph obtained by duplication of a vertex in \(K_{1,n}\) is an odd prime graph.
Proof. Let \(v_0\) be the apex vertex, and let \(v_1,v_2,\dots,v_n\) be the pendant vertices of \(K_{1,n}\). Let \(G\) be the graph obtained by duplication of a vertex \(v_j\) by a new vertex \(v_j'\). Then \(|V(G)|=n+2=N\). We consider the following cases.
Case (i). \(\deg(v_j)=n\), so \(v_j=v_0\).
In this case, \(v_0'\) is adjacent to all pendant vertices \(v_1,v_2,\dots,v_n\). By Bertrand’s Postulate, there exists a prime \(p\) such that \[n+1<p<2n+2.\] Since \(p\) is odd, we may write \(p=2k+1\) for some \(k\in\{1,2,\dots,n\}\). Define \[f:V(G)\to \{1,3,5,\dots,2N-1\}\] by \[f(v_i)=2i+1,\qquad 0\le i\le n,\] and \[f(v_0')=2n+3.\]
Now define \[h(x)=f(x),\qquad x\in V(G)\setminus\{v_k,v_0'\},\] \[h(v_k)=2n+3,\qquad h(v_0')=p.\]
We now show that \(h\) is bijective. The function \(f\) assigns the distinct labels \[1,3,5,\dots,2n+3\] to the vertices of \(G\), so \(f\) is a bijection. Since \(h\) is obtained from \(f\) only by interchanging the two labels assigned to \(v_k\) and \(v_0'\), the set of labels used by \(h\) is still exactly \[\{1,3,5,\dots,2n+3\}=\{1,3,5,\dots,2N-1\},\] and no two vertices receive the same label. Hence \(h\) is injective. Since both \(V(G)\) and the codomain have exactly \(N\) elements, it follows that \(h\) is bijective.
It remains to verify the gcd condition. Since the edges of \(G\) are exactly \[v_0v_j \quad \text{and} \quad v_0'v_j,\qquad 1\leq j\leq n,\] we check these two edge classes. For every \(1\leq i\leq n\), \[\gcd\bigl(h(v_0),h(v_i)\bigr)=\gcd(1,h(v_i))=1.\] Also, for every \(1\leq i\leq n\), \[\gcd\bigl(h(v_0'),h(v_i)\bigr)=\gcd(p,h(v_i)).\] Now \(p\) is prime, \(h(v_i)\ne p\) for every \(i\), and every label \(h(v_i)\) is an odd integer at most \(2n+3\). Since \(p>n+1\), we have \[3p>3n+3>2n+3.\] Thus, the only odd multiple of \(p\) in the set \(\{1,3,5,\dots,2n+3\}\) is \(p\) itself. Hence \(p\nmid h(v_i)\) for every \(i\), and therefore \[\gcd\bigl(h(v_0'),h(v_i)\bigr)=1,\qquad 1\leq i\leq n.\] Thus, \(h\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph in this case.
Case (ii). \(\deg(v_j)=1\), so \(v_j\) is a pendant vertex.
In this case, the duplicated vertex \(v_j'\) is also adjacent only to \(v_0\). Hence \(G\cong K_{1,n+1}\). By the preceding theorem, \(G\) is an odd prime graph. Therefore, the graph obtained by duplication of a vertex in \(K_{1,n}\) is an odd prime graph. ◻
Theorem 2.16. The graph obtained by duplication of a vertex by an edge in \(K_{1,n}\) is an odd prime graph.
Proof. Let \(v_0\) be the apex vertex, and let \(v_1,v_2,\dots,v_n\) be the pendant vertices of \(K_{1,n}\). Let \(G\) be the graph obtained by duplication of a vertex \(v_j\) in \(K_{1,n}\) by an edge \(v_j'v_j''\). Then \(|V(G)|=(n+1)+2=n+3=N\). We consider the following cases.
Case (i). \(\deg(v_j)=n\), so \(v_j=v_0\).
In this case, the new vertices \(v_0'\) and \(v_0''\) are adjacent to \(v_0\) and to each other. Define \[f:V(G)\to \{1,3,5,\dots,2N-1\}\] by \[f(v_0)=1,\qquad f(v_i)=2i+1,\quad 1\leq i\leq n,\] and \[f(v_0')=2n+3,\qquad f(v_0'')=2n+5.\]
We now show that \(f\) is bijective. The labels assigned by \(f\) are exactly \[1,3,5,\dots,2n+5=\{1,3,5,\dots,2N-1\},\] and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). We have \[\gcd(f(v_0),f(v_i))=\gcd(1,2i+1)=1,\qquad 1\leq i\leq n.\] Also, \[\gcd(f(v_0),f(v_0'))=\gcd(1,2n+3)=1,\] \[\gcd(f(v_0),f(v_0''))=\gcd(1,2n+5)=1,\] and \[\gcd(f(v_0'),f(v_0''))=\gcd(2n+3,2n+5)=\gcd(2n+3,2)=1.\] Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph in this case.
Case (ii). \(\deg(v_j)=1\), so \(v_j\) is a pendant vertex. Without loss of generality, assume that \(v_j=v_n\).
In this case, the new vertices \(v_n'\) and \(v_n''\) are adjacent to \(v_n\) and to each other. Define \[f:V(G)\to \{1,3,5,\dots,2N-1\}\] by \[f(v_0)=1,\qquad f(v_n)=3,\qquad f(v_n')=5,\qquad f(v_n'')=7,\] and \[f(v_i)=2i+7,\qquad 1\leq i\leq n-1.\]
We now show that \(f\) is bijective. The labels on \(v_1,v_2,\dots,v_{n-1}\) are \[9,11,\dots,2n+5.\] Together with the labels \(1,3,5,7\) assigned to \(v_0,v_n,v_n',v_n''\), the labels used by \(f\) are exactly \[1,3,5,\dots,2n+5=\{1,3,5,\dots,2N-1\},\] and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). We have \[\gcd(f(v_0),f(v_i))=\gcd(1,2i+7)=1,\qquad 1\leq i\leq n.\] Also, \[\gcd(f(v_0),f(v_n))=\gcd(1,3)=1,\] \[\gcd(f(v_n),f(v_n'))=\gcd(3,5)=1,\] \[\gcd(f(v_n),f(v_n''))=\gcd(3,7)=1,\] and \[\gcd(f(v_n'),f(v_n''))=\gcd(5,7)=1.\]
Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph in this case as well. Therefore, the graph obtained by duplication of a vertex by an edge in \(K_{1,n}\) is an odd prime graph. ◻
Theorem 2.17. The graph obtained by duplication of every vertex by an edge in \(K_{1,n}\) is an odd prime graph for \(n\geq 2\).
Proof. Let \(v_0\) be the apex vertex, and let \(v_1,v_2,\ldots,v_n\) be the pendant vertices of \(K_{1,n}\). Let \(G\) be the graph obtained by duplicating each vertex \(v_i\) of \(K_{1,n}\) by an edge \(v_i'v_i''\), for \(0\leq i\leq n\). Then \[|V(G)|=3(n+1)=3n+3=N.\] Define \[f:V(G)\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_i)=6i+1,\qquad 0\leq i\leq n,\] \[f(v_i')=6i+3,\qquad 0\leq i\leq n,\] and \[f(v_i'')=6i+5,\qquad 0\leq i\leq n.\]
We now show that \(f\) is bijective. The labels assigned by \(f\) are exactly \[1,3,5,7,9,11,\ldots,6n+1,6n+3,6n+5,\] that is, all odd integers from \(1\) to \(6n+5=2N-1\), and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain \(\{1,3,5,\ldots,2N-1\}\) have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). We have \[\gcd(f(v_0),f(v_i))=\gcd(1,6i+1)=1,\qquad 1\leq i\leq n,\] \[\gcd(f(v_i),f(v_i'))=\gcd(6i+1,6i+3)=\gcd(6i+1,2)=1,\qquad 1\leq i\leq n,\] \[\gcd(f(v_i),f(v_i''))=\gcd(6i+1,6i+5)=\gcd(6i+1,4)=1,\qquad 1\leq i\leq n,\] and \[\gcd(f(v_i'),f(v_i''))=\gcd(6i+3,6i+5)=\gcd(6i+3,2)=1,\qquad 1\leq i\leq n.\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.18. The graph obtained by duplication of an edge by a vertex in \(K_{1,n}\) is an odd prime graph.
Proof. Let \(v_0\) be the apex vertex, and let \(v_1,v_2,\ldots,v_n\) be the pendant vertices of \(K_{1,n}\). Let \(G\) be the graph obtained by duplication of the edge \(v_0v_n\) in \(K_{1,n}\) by a new vertex \(v_n'\). Then \[|V(G)|=(n+1)+1=n+2=N.\] Define \[f:V(G)\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_i)=2i+1,\qquad 0\leq i\leq n,\] and \[f(v_n')=2n+3.\]
We now show that \(f\) is bijective. The labels assigned by \(f\) are exactly \[1,3,5,\ldots,2n+3=\{1,3,5,\ldots,2N-1\},\] and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain \(\{1,3,5,\ldots,2N-1\}\) have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). We have \[\gcd(f(v_0),f(v_i))=\gcd(1,2i+1)=1,\qquad 1\leq i\leq n.\] Also, \[\gcd(f(v_0),f(v_n'))=\gcd(1,2n+3)=1,\] and \[\gcd(f(v_n),f(v_n'))=\gcd(2n+1,2n+3)=\gcd(2n+1,2)=1.\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.19. The graph obtained by duplication of every edge by a vertex of \(K_{1,n}\) is an odd prime graph.
Proof. Let \(v_0\) be the apex vertex, and let \(v_1,v_2,\ldots,v_n\) be the pendant vertices of \(K_{1,n}\). Let \(G\) be the graph obtained by duplication of each edge \(v_0v_i\) by a new vertex \(v_i'\), for \(1\leq i\leq n\). Then \[|V(G)|=(n+1)+n=2n+1=N.\] Define \[f:V(G)\to \{1,3,5,\dots,2N-1\}\] by \[f(v_i)=4i+1,\qquad 0\leq i\leq n,\] and \[f(v_i')=4i-1,\qquad 1\leq i\leq n.\]
We now show that \(f\) is bijective. The labels on the original vertices are \[1,5,9,\dots,4n+1,\] and the labels on the new vertices are \[3,7,11,\dots,4n-1.\] Together, these are exactly all odd integers from \(1\) to \(4n+1=2N-1\), and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain \(\{1,3,5,\dots,2N-1\}\) have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). We have \[\gcd(f(v_0),f(v_i))=\gcd(1,4i+1)=1,\qquad 1\leq i\leq n,\] and \[\gcd(f(v_0),f(v_i'))=\gcd(1,4i-1)=1,\qquad 1\leq i\leq n.\] Also, \[\gcd(f(v_i),f(v_i'))=\gcd(4i+1,4i-1)=\gcd(4i-1,2)=1,\qquad 1\leq i\leq n.\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Lemma 2.20. Let \(p\) be the greatest prime number less than or equal to an integer \(n\geq2\). Then \[3p>n.\]
Proof. We proceed by contradiction. Suppose, on the contrary, that \(3p\leq n\). Let \[m=\left\lfloor \frac{n}{3}\right\rfloor.\] Then, by our assumption, all prime numbers less than or equal to \(n\) are at most \(m\). In other words, the interval \((m,n]\) contains no prime numbers.
However, by Bertrand’s Postulate, for every integer \(x>1\), there exists at least one prime number \(q\) such that \[x<q<2x.\] Applying the postulate to \(x=\frac{n}{2}\), we obtain a prime \(q\) such that \[\frac{n}{2}<q<n.\] Since \[m=\left\lfloor \frac{n}{3}\right\rfloor < \frac{n}{2}<q<n,\] there exists a prime \(q\) in the interval \((m,n)\), contradicting the assumption that \(p\leq m\) is the largest prime less than or equal to \(n\). This contradiction implies that our assumption was false. Therefore, \[3p>n.\] ◻
Theorem 2.21. The graph obtained by duplication of an edge in \(K_{1,n}\) is an odd prime graph.
Proof. The result is immediate for \(n=1,2\). Hence assume that \(n\geq3\). Let \(v_0\) be the apex vertex, and let \(v_1,v_2,\dots,v_n\) be the pendant vertices of \(K_{1,n}\). Since every edge of \(K_{1,n}\) is of the form \(v_0v_j\) for some \(j\), we may assume without loss of generality that \(e=v_0v_n\). Let \(G\) be the graph obtained by duplication of the edge \(e=v_0v_n\) by a new edge \(e'=v_0'v_n'\). Then \[|V(G)|=(n+1)+2=n+3=N.\]
By Bertrand’s Postulate, there exists a prime \(p\) such that \[n+1<p<2n+2.\] Since \(p\) is odd, we may write \[p=2k+1\] for some integer \(k\). From \(p<2n+2\), we get \(k\leq n\), and since \(p\geq3\), we have \(k\geq1\). Thus, \[k\in\{1,2,\dots,n\}.\] Also, \[p<2n+2<2n+3<2n+5,\] so, in particular, \[p\neq 2n+3 \qquad \text{and} \qquad p\neq 2n+5.\]
Define \[f:V(G)\to \{1,3,5,\dots,2N-1\}\] by \[f(v_i)=2i+1,\qquad 0\leq i\leq n,\] and \[f(v_0')=2n+3,\qquad f(v_n')=2n+5.\]
Now define \[h(x)=f(x),\qquad x\in V(G)\setminus\{v_k,v_0'\},\] \[h(v_k)=2n+3,\qquad h(v_0')=p,\] and \[h(v_n')=2n+5.\]
We now show that \(h\) is bijective. The function \(f\) assigns the distinct labels \[1,3,5,\dots,2n+5\] to the vertices of \(G\), so \(f\) is injective. Since both \(V(G)\) and the codomain \(\{1,3,5,\dots,2N-1\}\) have exactly \(N\) elements, \(f\) is bijective. Since \(h\) is obtained from \(f\) only by interchanging the two labels assigned to \(v_k\) and \(v_0'\), the set of labels used by \(h\) is still exactly \[\{1,3,5,\dots,2n+5\}=\{1,3,5,\dots,2N-1\},\] and no two vertices receive the same label. Hence \(h\) is injective. Since both \(V(G)\) and the codomain have exactly \(N\) elements, it follows that \(h\) is bijective.
It remains to verify that \(\gcd(h(u),h(v))=1\) for every edge \(uv\) of \(G\). For every \(1\leq i\leq n\), we have \[\gcd\bigl(h(v_0),h(v_i)\bigr)=\gcd(1,h(v_i))=1.\] Next, for every \(1\leq i\leq n-1\), we have \[\gcd\bigl(h(v_0'),h(v_i)\bigr)=\gcd(p,h(v_i)).\] Now \(p\) is prime, and \(h(v_i)\neq p\) for every \(1\leq i\leq n-1\), since the only vertex with label \(p\) is \(v_0'\). If \[\gcd\bigl(h(v_0'),h(v_i)\bigr)\neq1,\] then \(p\mid h(v_i)\). Since \(h(v_i)\) is odd and \(h(v_i)\neq p\), we must have \(h(v_i)\geq3p\). But \(p>n+1\), so \[3p>3n+3>2n+5,\] which is impossible, because every label of \(h\) belongs to \(\{1,3,5,\dots,2n+5\}\). Hence \[\gcd\bigl(h(v_0'),h(v_i)\bigr)=1,\qquad 1\leq i\leq n-1.\]
Finally, \[\gcd\bigl(h(v_0'),h(v_n')\bigr)=\gcd(p,2n+5).\] Again, \(p\) is prime and \(p\neq2n+5\). If \(\gcd(p,2n+5)\neq1\), then \(p\mid(2n+5)\). Since \(2n+5\) is odd and distinct from \(p\), we must have \(2n+5\geq3p\), which is impossible because \(3p>2n+5\). Therefore, \[\gcd\bigl(h(v_0'),h(v_n')\bigr)=1.\]
Thus, \(\gcd\bigl(h(u),h(v)\bigr)=1\) for every edge \(uv\) of \(G\). Hence \(h\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.22. The graph obtained by duplication of a vertex by an edge in \(C_n\) is an odd prime graph.
Proof. Let \(v_1,v_2,\ldots,v_n\) be the consecutive vertices of \(C_n\). Let \(G\) be the graph obtained by duplication of the vertex \(v_1\) in \(C_n\) by a new edge \(v_1'v_1''\). Then \[|V(G)|=n+2=N.\] Define \[f:V(G)\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_i)=2i-1,\qquad 1\leq i\leq n,\] and \[f(v_1')=2n+1,\qquad f(v_1'')=2n+3.\]
We now show that \(f\) is bijective. The labels assigned by \(f\) are exactly \[1,3,5,\ldots,2n+3=\{1,3,5,\ldots,2N-1\},\] and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain \(\{1,3,5,\ldots,2N-1\}\) have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). For each \(1\leq i\leq n-1\), we have \[\gcd(f(v_i),f(v_{i+1})) =\gcd(2i-1,2i+1) =\gcd(2i-1,2)=1.\] Also, \[\gcd(f(v_1),f(v_n))=\gcd(1,2n-1)=1,\] \[\gcd(f(v_1),f(v_1'))=\gcd(1,2n+1)=1,\] \[\gcd(f(v_1),f(v_1''))=\gcd(1,2n+3)=1,\] and \[\gcd(f(v_1'),f(v_1''))=\gcd(2n+1,2n+3)=\gcd(2n+1,2)=1.\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.23. The graph obtained by duplication of every vertex by an edge in \(C_n\) is an odd prime graph.
Proof. Let \(v_1,v_2,\ldots,v_n\) be the consecutive vertices of \(C_n\). Let \(G\) be the graph obtained by duplicating each vertex \(v_i\) of \(C_n\) by an edge \(v_i'v_i''\), for \(1\leq i\leq n\). Then \[|V(G)|=3n=N.\] Define \[f:V(G)\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_i)=6i-5,\qquad 1\leq i\leq n,\] \[f(v_i')=6i-3,\qquad 1\leq i\leq n,\] and \[f(v_i'')=6i-1,\qquad 1\leq i\leq n.\]
We now show that \(f\) is bijective. The labels assigned by \(f\) are exactly \[1,3,5,7,9,11,\ldots,6n-5,6n-3,6n-1,\] that is, all odd integers from \(1\) to \(6n-1=2N-1\), and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain \(\{1,3,5,\ldots,2N-1\}\) have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). We have \[\gcd(f(v_i),f(v_{i+1})) =\gcd(6i-5,6i+1) =\gcd(6i-5,6)=1,\qquad 1\leq i\leq n-1.\] Also, \[\gcd(f(v_n),f(v_1))=\gcd(6n-5,1)=1.\] For each \(1\leq i\leq n\), we have \[\gcd(f(v_i),f(v_i')) =\gcd(6i-5,6i-3) =\gcd(6i-5,2)=1,\] \[\gcd(f(v_i),f(v_i'')) =\gcd(6i-5,6i-1) =\gcd(6i-5,4)=1,\] and \[\gcd(f(v_i'),f(v_i'')) =\gcd(6i-3,6i-1) =\gcd(6i-3,2)=1.\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.24. The graph obtained by duplication of every edge by a vertex in \(C_n\) is an odd prime graph.
Proof. Let \(v_1,v_2,\ldots,v_n\) be the consecutive vertices of \(C_n\). Let \(G\) be the graph obtained by duplication of all the edges \[v_1v_2,\; v_2v_3,\; \ldots,\; v_{n-1}v_n,\; v_nv_1\] by new vertices \(u_1,u_2,\ldots,u_n\), respectively. Then \[|V(G)|=n+n=2n=N.\] Define \[f:V(G)\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_i)=4i-3,\qquad 1\leq i\leq n,\] and \[f(u_i)=4i-1,\qquad 1\leq i\leq n.\]
We now show that \(f\) is bijective. The labels assigned to the vertices \(v_1,v_2,\ldots,v_n\) are \[1,5,9,\ldots,4n-3,\] and the labels assigned to the vertices \(u_1,u_2,\ldots,u_n\) are \[3,7,11,\ldots,4n-1.\] Together, these are exactly all odd integers from \(1\) to \(4n-1=2N-1\), and they are all distinct. Hence \(f\) is injective. Since both \(V(G)\) and the codomain \(\{1,3,5,\ldots,2N-1\}\) have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). We have \[\gcd(f(v_i),f(v_{i+1})) =\gcd(4i-3,4i+1) =\gcd(4i-3,4)=1,\qquad 1\leq i\leq n-1.\] Also, \[\gcd(f(v_n),f(v_1))=\gcd(4n-3,1)=1.\] For each \(1\leq i\leq n\), we have \[\gcd(f(v_i),f(u_i)) =\gcd(4i-3,4i-1) =\gcd(4i-3,2)=1.\] Moreover, \[\gcd(f(u_i),f(v_{i+1})) =\gcd(4i-1,4i+1) =\gcd(4i-1,2)=1,\qquad 1\leq i\leq n-1.\] Also, \[\gcd(f(u_n),f(v_1))=\gcd(4n-1,1)=1.\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻
Theorem 2.25. The graph obtained by duplication of an edge in \(C_n\) is an odd prime graph.
Proof. We assume that \(n\geq5\), since the result is immediate for \(n=3,4\). Let \(v_1,v_2,\ldots,v_n\) be the consecutive vertices of \(C_n\). Let \(G\) be the graph obtained by duplication of the edge \(v_1v_n\) in \(C_n\) by a new edge \(v_1'v_n'\). Then \[|V(G)|=n+2=N.\] Define \[f:V(G)\to \{1,3,5,\ldots,2N-1\}\] by \[f(v_{n-1})=1,\qquad f(v_2)=3,\qquad f(v_1)=5,\] \[f(v_1')=7,\qquad f(v_n)=9,\qquad f(v_n')=11,\] and \[f(v_i)=2i+7,\qquad 3\leq i\leq n-2.\]
We now show that \(f\) is bijective. The labels assigned to \[v_{n-1},\,v_2,\,v_1,\,v_1',\,v_n,\,v_n'\] are \[1,3,5,7,9,11,\] respectively. For \(3\leq i\leq n-2\), the labels \(f(v_i)=2i+7\) are precisely \[13,15,\ldots,2n+3.\] Hence the labels assigned by \(f\) are exactly \[1,3,5,\ldots,2n+3=\{1,3,5,\ldots,2N-1\},\] and they are all distinct. Therefore \(f\) is injective. Since both \(V(G)\) and the codomain have exactly \(N\) elements, it follows that \(f\) is bijective.
It remains to verify that \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). First, for the special cycle edges, we have \[\gcd(f(v_1),f(v_2))=\gcd(5,3)=1,\] \[\gcd(f(v_{n-1}),f(v_n))=\gcd(1,9)=1,\] and \[\gcd(f(v_n),f(v_1))=\gcd(9,5)=1.\] For the remaining cycle edges, we have \[\gcd(f(v_i),f(v_{i+1})) =\gcd(2i+7,2i+9) =\gcd(2i+7,2)=1,\qquad 3\leq i\leq n-3.\] Also, \[\gcd(f(v_2),f(v_3))=\gcd(3,13)=1,\] and \[\gcd(f(v_{n-2}),f(v_{n-1}))=\gcd(2n+3,1)=1.\] For the new edges, we have \[\gcd(f(v_2),f(v_1'))=\gcd(3,7)=1,\] \[\gcd(f(v_1'),f(v_n'))=\gcd(7,11)=1,\] and \[\gcd(f(v_n'),f(v_{n-1}))=\gcd(11,1)=1.\]
Therefore, \(\gcd(f(u),f(v))=1\) for every edge \(uv\) of \(G\). Hence \(f\) is an odd prime labeling of \(G\), and consequently \(G\) is an odd prime graph. ◻