(2,1)-total labeling of trees with large maximum degree

A k-(2, 1)-total labeling of a graph G is to label the vertices and the edges of G using integers from 0 to k such that all adjacent vertices as well as edges receive different labels, and the difference between the labels of a vertex and its incident edges is at least 2. The (2, 1)-total labeling number lambda(t)(2)(G) is the smallest integer k such that G has a k-(2, 1)-total labeling. It is known that lambda(t)(2)(T), where T is a tree with maximum degree Delta, equals to either Delta + 1 or Delta + 2. In this paper, we provide a sufficient condition for a tree T to have lambda(t)(2)(T) = Delta + 1 when Delta >= 9. (C) 2015 Elsevier B.V. All rights reserved.