The -total labeling problem for trees

A ( p , q ) -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 of nonnegative integers such that | f ( x ) − f ( y ) | ≥ p if x is a vertex and y is an edge incident to x , and | f ( x ) − f ( y ) | ≥ q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V ( G ) ∪ E ( G ) . A k - ( p , q ) -total labeling is a ( p , q ) -total labeling f : V ( G ) ∪ E ( G ) → { 0 , … , k } , and the ( p , q ) -total labeling problem asks the minimum k , which we denote by λ p , q T ( G ) , among all possible assignments. In this paper, we first give new upper and lower bounds on λ p , q T ( G ) for some classes of graphs G , in particular, tight bounds on λ p , q T ( T ) for trees T . We then show that if p ≤ 3 q / 2 , the problem for trees T is linearly solvable, and completely determine λ p , q T ( T ) for trees T with Δ ≥ 4 , where Δ is the maximum degree of T . It is contrasting to the fact that the L ( p , q ) -labeling problem, which is a generalization of the ( p , q ) -total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p .