We consider only finite, simple and undirected graphs. For a graph G, its vertex and edge sets are denoted by V (G) and E (G) respectively and further, |V (G)| and |E (G)| denote their cardinalities. Definition 1.1. A bijection f: V (G)! {1, 2, 3, n} is said to be a prime labeling of a graph G with n vertices, if f (u) and f (v) are relatively prime numbers (i.e., Gcd (f (u), f (v)) = 1) whenever u are v are adjacent vertices of G. Since the introduction of prime labeling about thirty five years ago, varieties of graphs have been studied for prime labeling. A brief summary of the results regarding prime labeling and its variants is available in the dynamic survey of graph labeling maintained by Gallian [3]. In this paper, we mainly investigate prime labeling for graphs which are union of C (k) n (defined below).