Some new results on strongly prime graphs

A graphG  (V,E) with n vertices is said to admit prime labeling if its vertices can be labeled with distinct positive integers not exceeding n such that the label of each pair of adjacent vertices are relatively prime. A graph G which admits prime labeling is called a prime graph and a graph G is said to be a strongly prime graph if for any vertex v of G there exists a prime labeling f satisfying f v 1. In this paper we prove that the graphs n bk P C , * bk n C C , k n C P , 1 G K where G is a ( ) n n C C graph and splitting graph of 1,n K are strongly prime graphs.