On (s, t)-relaxed L(1, 1)-labelling of trees. Issue 6 (3rd June 2017) - Lin, Wensong; Zhao, Xuan
ABSTRACT: Suppose G is a graph. Let u be a vertex of G . A vertex v is called an i -neighbour of u ifd G ( 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 withf ( v ) = f ( u ) (resp.f ( w ) = f ( u ) ) is at most s (resp. t ), then f is called an( s, t ) -relaxedL ( 1, 1 ) -labelling of G . The span of f, denoted byspan ( f ), is the difference between the maximum and minimum integers used by f . The minimum span of( s, t ) -relaxedL ( 1, 1 ) -labellings of G is called the( s, t ) -relaxedL ( 1, 1 ) -labelling number of G, denoted byλ 1, 1 s, t ( G ) . It is clear thatλ 1, 1 0, 0 ( G ) is the so calledL ( 1, 1 ) -labelling number of G . This paper studies the( s, t ) -relaxedL ( 1, 1 ) -labellings of trees. Let T be a tree with maximum degree Δ. It is proved that⌈ ( Δ − s ) / ( t + 1 ) ⌉ ≤ λ 1, 1 s, t ( T ) ≤ ⌈ ( Δ − s + t ) / ( t + 1 ) ⌉ and both lower and upper bounds are attainable. For s =0 andt ≥ 1 fixed, a polynomial-time algorithm is designed to determine ifλ 1, 1 s, t ( T ) equals the lower bound.