A complete \(L (2, 1)\) span characterization for small trees (Q896092)

An \(L(2, 1)\) labeling of a graph \(G\) is a mapping \(f : V (G)\) to the set of nonnegative integers, such that \(|f(u)-f(v)|\geq 2\) if \(uv\in E(G)\) and \(|f(u)-f(v)|\geq 1\) otherwise. The span of an \(L(2, 1)\) labeling \(f\) on a graph \(G\) is the maximum \(f(u)\) for all \(u\in V (G)\). The \(L(2, 1)\) span \(\lambda(G)\) of a graph \(G\) is the minimum span of all \(L(2, 1)\) labelings on \(G\). \textit{J. R. Griggs} and \textit{R. K. Yeh} [SIAM J. Discrete Math. 5, No. 4, 586--595 (1992; Zbl 0767.05080)] showed that \(\lambda(T)\in \{\Delta(T)+1, \Delta(T)+2\}\) for a tree \(T\) of maximum degree \(\Delta(T)\). \textit{G. J. Chang} and \textit{D. Kuo} [ibid. 9, No. 2, 309--316 (1996; Zbl 0860.05064)] provided a polynomial-time algorithm that can decide whether or not \(\lambda(T)=\Delta(T)+ 1\). In the current paper, the authors present a complete characterization of \(\lambda(T)\) for trees \(T\) up to twenty vertices in terms of forbidden subtrees.