The L(2,1)-labeling and operations of graphs
Zhendong Shao, Roger K. Yeh · IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications · 2005
Motivated by a variation of the channel assignment problem, a graph labeling analogous to the graph vertex coloring has been presented and is called an L(2,1)-labeling. More precisely, an L(2,1)-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(x)-f(y)| /spl ges/ 2 if d(x,y)=1 and |f(x)-f(y)| /spl ges/ 1 if d(x,y) = 2. The L(2,1)-labeling number /spl lambda/(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v/spl isin/V(G)}=k. A conjecture states that /spl lambda/(G) /spl les/ /spl Delta//sup 2/ for any simple graph with the maximum degree /spl Delta//spl ges/2. This paper considers the graphs formed by the Cartesian product and the composition of two graphs. The new graph satisfies the conjecture above in both cases(with minor exceptions).