Prime labeling on graphs

Abstract

The notion of prime labeling originated with Entringer and was introduced in a paper by Taut, Dabboucy and Howalla. A graph with vertex set V is said to have prime labeling if there exist a bijection f: V (G)  {1,2,..., V  } such that for each edge xy  E(G), f(x) and f(y) are relatively prime. Among the classes of graphs known to have prime labeling are: Paths, Stars, and Caterpillar, Spider , Complete Binary trees, nP2, Union of paths, Bistar Bn,n and < K1,n: 2 >.In this paper we construct some connected simple graphs G (V, E) without self loops and multiple edges. We present algorithms to assign prime labeling and thereby prove the existence of prime labeling using the techniques of Number theory for some class of connected and disconnected graphs: (Pm  nK1) + N2, (Cm  nK1) + N2 , (Pm Cn  rK1) + N2 , CnCn+1, and CnmPk.