L(1,1,1)-labeling of path, bouquet of cycles and sun graph

Abstract

For a given graph G(V,E), L(1,1,1)-labeling problem is an assignment from vertex set V to the set of non negative integers. If Z^+ be the non negative integers then L(1,1,1)-labeling is a function f:V→Z^+ such that for any two vertices x and y, |f(x)-f(y)|≥1, when d(x,y)=1; |f(x)-f(y)|≥1, when d(x,y)=2; and |f(x)f(y)|≥1, when d(x,y)=3. The L(1,1,1)-chromatic number λ_1,1,1 is the smallest positive integer such that G has an L(1,1,1)-labeling with λ_1,1,1 as the maximum label. In this paper we determine the L(1,1,1)-chromatic number for a path, a cycle, bouquet of cycles joining at a vertex (all are of finite lengths) and sun graph. We also present a lower and upper bounds for λ_1,1,1 in terms of the maximum degree of G.