On (s, t)-relaxed L(1, 1)-labelling of trees. Issue 6 (3rd June 2017)

• Record Type: Journal Article
• Authors: Lin, Wensong; Zhao, Xuan
• Is Part Of: International journal of computer mathematics. Volume 94:Issue 6(2017)
• Page Start: 1219
• Page End: 1227
• Publication Date: 2017-06-03
• Subjects: L(j, k)-labelling -- (s, t)-relaxed L(1, 1)-labelling -- tree -- complete Δ-regular tree -- channel assignment; 05C15; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2016.1188922
• Languages: English
• ISSNs: 0020-7160

Abstract

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.