Optimal $L(2,1,1)$-Labelings of Caterpillars
Received:February 24, 2022  Revised:May 21, 2022
Key Words: channel assignment   $L(2,1,1)$-labeling   span   caterpillar
Fund Project:Supported by the National Natural Science Foundation of China (Grant No.11601265) and the Scientific Research Foundation of Jimei University (Grant No.Q202201).
 Author Name Affiliation Xiaoling ZHANG Teachers College, Jimei University, Fujian 361021, P. R. China
Hits: 25
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$.