The L(2, 1, 1)-labellings of caterpillars. Issue 3 (1st October 2016)

• Record Type: Journal Article
• Authors: Zhang, Xiaoling; Deng, Kecai
• Is Part Of: International journal of computer mathematics. Volume 1:Issue 3/4(2016)
• Page Start: 85
• Page End: 97
• Publication Date: 2016-10-01
• Subjects: Channel assignment -- L(2, 1, 1)-labelling -- span -- tree -- caterpillar; 05C15; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2016.1262902
• Languages: English
• ISSNs: 2379-9927

Abstract

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 .