Duplication operations on some families of odd prime graphs

Abstract

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) → {1, 3, 5, …, 2n − 1}, where n = |V(G)|, such that gcd (f(x), f(y)) = 1 for every edge xy ∈ 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 Pn, the cycle graph Cn, and the star graph K1, n under various vertex- and edge-duplication constructions.