The L(2, 1, 1)-labellings of caterpillars. Issue 3 (1st October 2016) - Zhang, Xiaoling; Deng, Kecai
ABSTRACT: An -labelling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all -labellings of G is called the -labelling number of G, denoted by . It was shown by King, Ras and Zhou [The -labelling problem for trees, Europ. J. Combinatorics 31 (2010), pp. 1295–1306] that every tree T has, where . In this paper, we provide some sufficient conditions for . Furthermore, we completely characterize the -labelling numbers of caterpillars with . For, we prove that the -labelling numbers of caterpillars with no vertices of degree at distance 3 or 4 k +2 attain the lower bound. And we show that there always exists one tree T with two vertices of degree at distance 3 or 4 k +2 attaining the upper bound for any .