International Journal of Computer Science Issues

More than a traditional journal...

The concept of L(2,1)-labeling in graph came into existence with the solution of frequency assignment problem. In fact, in this problem a frequency in the form of nonnegative integers is to assign to each radio or TV transmitters located at various places such that communication does not interfere. This frequency assignment problem can be modeled with vertex labeling of graphs. An L(2,1)-labeling (or distance two labeling) of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(u)-f(v)|2 if d(u,v)=1 and |f(u)-f(v)|1 if d(u,v)=2, where d(u,v) denotes the distance between u and v in G. The L(2,1)-labeling number (G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v ϵ V(G) }=k. This paper consider the L(2,1)-labeling number for the homomorphic product of two graphs and it is proved that Griggs and Yehs conjecture is true for the homomorphic product of two graphs with minor exceptions.