Prime Labeling of Newly Constructed Graph Using Star Graphs and Complete Bipartite Graphs

A graph G=(V(G),E(G))with |V(G)| vertices is said to have prime labeling if there exist a bijection map f∶V(G) → {1,2,3,…,|V(G)|} such that for each edge e=uv in E(G), f(u) and f(v) are relatively prime. A graph G which admits prime labeling is called a prime graph. Two integers are said to be relatively prime, if their greatest common divisor (g.c.d) is 1. A complete bipartite graph is a simple bipartite graph in which each vertex in one partite set is adjacent to all the vertices in the other partite set. AKp,q graph is a complete bipartite graph which has p vertices in one partite set and q vertices in other partite set, where p,q≥1. If p=1, then K1,q graph is called a star graph. The present work focuses on prime labeling on simple finite undirected graphs related to star graph. In our work, we proved the graphs obtained by replacing every edge of a star graph K1,n by K2,m is a prime graph, where n≥1 for m=4,8,9 and 1≤n≤16 for m=6.