Prime labeling of a star graph

Abstract

A graph 𝐺=(𝑉(𝐺),𝐸(𝐺)) with |𝑉(𝐺)| vertices is said to have prime labeling if there exist a bijective map 𝑓∶𝑉(𝐺) → {1,2,3,…,|𝑉(𝐺)|} such that for each edge 𝑒=𝑢𝑣 in 𝐸(𝐺), f (u) and f (v) are relatively prime. A graph G which admits prime labeling is called a prime graph. 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. A Kp,q graph is a complete bipartite graph which has p vertices in one partite set and q vertices in other partite set, where p,𝑞≥1. If 𝑝=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. We proved that the graphs obtained by replacing every edge of star graph K1,n by K2,5 is a prime graph, where 𝑛 ≥ 1.