The $L(2,1)$-Labeling Problem on Graphs

Source abstract

An $L(2,1)$-labeling of a graph G is a function f from the vertex set $V(G)$ to the set of all nonnegative integers such that $| f(x) - f(y) | \geq 2$ if $d(x,y) = 1$ and $| f(x) - f(y) | \geq 1$ if $d(x,y) = 2$. The $L(2,1)$-labeling number $\lambda (G)$ of G is the smallest number k such that G has an $L(2,1)$-labeling with $\max\{ f(v ):v \in V(G) \} = k$. In this paper, we give exact formulas of $\lambda (G \cup H)$ and $\lambda (G + H)$. We also prove that $\lambda (G) \leq \Delta ^2 + \Delta$ for any graph G of maximum degree $\Delta$. For odd-sun-free (OSF)-chordal graphs, the upper bound can be reduced to $\lambda (G) \leq 2\Delta + 1$. For sun-free (SF)-chordal graphs, the upper bound can be reduced to $\lambda (G) \leq \Delta + 2\chi (G) - 2$. Finally, we present a polynomial time algorithm to determine $\lambda (T)$ for a tree T.