The (p,q)(p,q)-total labeling problem for trees

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