On (s,t)-relaxed L(1,1)-labelling of trees

Suppose G is a graph. Let u be a vertex of G. A vertex v is called an ineighbour of u if dG(u, v) = i. A 1-neighbour of u is simply called a neighbour of u. Let s and t be two non-negative integers. Suppose f is an assignment of non-negative integers to the vertices of G. If, for any vertex u of G, the number of neighbours v (resp. 2-neighbours w) of u with f (v) = f (u) (resp. f (w) = f (u)) is at most s (resp. t), then f is called an (s, t)relaxed L(1, 1)-labelling of G. The span of f, denoted by span(f), is the difference between the maximum and minimum integers used by f. The minimum span of (s, t)-relaxed L(1, 1)-labellings of G is called the (s, t)-relaxed L(1, 1)-labelling number of G, denoted by. s, t 1,1(G). It is clear that. 0,0 1,1(G) is the so called L(1, 1)-labelling number of G. This paper studies the (s, t)relaxed L(1, 1)-labellings of trees. Let T be a tree with maximum degree Delta. It is proved that Delta (Delta -s)/(t + 1) Delta =. s, t 1,1(T) = Delta (Delta -s + t)/(t + 1) Delta and both lower and upper bounds are attainable. For s= 0 and t = 1 fixed, a polynomial-time algorithm is designed to determine if. s, t 1,1(T) equals the lower bound.