ABSTRACT
Suppose G is a graph. Let u be a vertex of G. A vertex v is called an i-neighbour of u if
. 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
(resp.
) is at most s (resp. t), then f is called an
-relaxed
-labelling of G. The span of f, denoted by
, is the difference between the maximum and minimum integers used by f. The minimum span of
-relaxed
-labellings of G is called the
-relaxed
-labelling number of G, denoted by
. It is clear that
is the so called
-labelling number of G. This paper studies the
-relaxed
-labellings of trees. Let T be a tree with maximum degree Δ. It is proved that
and both lower and upper bounds are attainable. For s=0 and
fixed, a polynomial-time algorithm is designed to determine if
equals the lower bound.
2010 AMS SUBJECT CLASSIFICATION:
Disclosure statement
No potential conflict of interest was reported by the authors.