The (p,q)-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

$\lambda^T_{p,q}(G)$

, among all possible assignments. In this paper, we first give new upper and lower bounds on

$\lambda^T_{p,q}(G)$

for some classes of graphs

G

, in particular, tight bounds on

$\lambda^T_{p,q}(T)$

for trees

T

. We then show that if

p

 ≤ 3

q

/2, the problem for trees

T

is linearly solvable, and give a complete characterization of trees achieving

$\lambda^T_{p,q}(T)$

if in addition Δ ≥ 4 holds, 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

.