k-PRIME LABELING OF UNION OF PATH GRAPH

Abstract

Let G be a simple graph, connected, and undirected graph G = (V (G);E(G))
with n vertices. Injective labeling on V (G) is said to be prime if each pair of adjacent
vertices has a relative prime labels. From the development of prime labeling it is de-
veloped a new concept on k􀀀prime labeling. A k􀀀prime labeling of a graph G is an
injective function f : V (G) ! fk; k+1; k+2; :::; k +jV (G)j􀀀1g for some positive integer
k that induces a function f+ : E(G) 􀀀! N which N is the set of neightboring vertices
and on the edges of G dened by f+(uv) = gcd(f(u); f(v)), for all uv in E(G) such
that gcd(f(u); f(v)) = 1. A graph G that admits k􀀀prime labeling is called a k􀀀prime
graph. In this paper, it will be discussed about k􀀀prime labeling of some graphs such
as one point union of path graphs Pt
n for n 1 and t 5, Pn;CmmK1;r graphs for
n 3;m = 3; 4; 5, and r 2, and also Pn(Pq;K1) graphs for n 2 and q even.