Abstract:

The authors gave some general propositions of L(d,1,1)labeling. An upper bound of λ_d,1,1(G) was given for any graph with maximum degree Δ by an algorithm which is λ_d,1,1(G)≤Δ³-Δ²+dΔ. For any tree of maximum degree Δ, we have d+Δ-1≤λd,1,1(T)≤d+2Δ-2, moreover, the lower and upper bounds are both attainable. The values of L(d,1,1)labeling number for quasi regular tree T_Δ and any regular caterpillar Cat_nwere also given, for d≥2.

Key words: graph labeling, L(d,1,1)labeling, frequency assignment, tree