Optimal $L(2,1,1)$-Labelings of Caterpillars

Abstract:

      An $L(2,1,1)$-labeling of a graph $G$ is an assignment of non-negative integers (labels) to the vertices of $G$ such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labeling is the difference between the maximum and minimum labels used, and the minimum span over all $L(2, 1, 1)$-labelings of $G$ is called the $L(2,1,1)$-labeling number of $G$, denoted by $\lambda_{2,1,1}(G)$. In this paper, we investigate the $L(2,1,1)$-labelings of caterpillars. Some useful sufficient conditions for $\lambda_{2,1,1}(T)=\Delta_2(T) = \max_{uv\in E(T)}(d(u) + d(v))$) are given. Furthermore, we show that the sufficient conditions we provide are also necessary for caterpillars with $\Delta_2(T)= 6$.