A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs

A (2, 1)-total labeling of a graph G is an assignment f from the vertex set V (G) and the edge set E(G) to the set {0, 1,..., k} of nonnegative integers such that |f (x) - f (y)| >= 2 if x is a vertex and y is an edge incident to x, and |f (x) - f (y)| >= 1 if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) boolean OR E(G). The (2, 1)-total labeling number lambda(T)(2) (G) of G is defined as the minimum k among all possible (2, 1)-total labelings of G. In 2007, Chen and Wang conjectured that all outerplanar graphs G satisfy lambda(T)(2) (G) <= Delta(G) + 2, where Delta(G) is the maximum degree of G. They also showed that it is true for G with Delta(G) >= 5. In this paper, we solve their conjecture, by proving that lambda(T)(2) (G) <= Delta(G) + 2, even when Delta(G) <= 4. (C) 2011 Elsevier B. V. All rights reserved.