毛毛虫树的最优$L(2,1,1)$-标号

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

中文关键词:  频率分配  $L(2,1,1)$-标号  标号数  毛毛虫树

英文关键词:channel assignment  $L(2,1,1)$-labeling  span  caterpillar

中文摘要:

      图$G$的一个$L(2,1,1)$-标号是指从顶点集$V(G)$到非负整数集上的一个函数$f$,满足: 当$d(u,v)=1$时, $|f(u)-f(v)|\ge 2$, 当$d(u,v)=2$时, $|f(u)-f(v)|\ge 1$, 当$d(u,v)=3$时, $|f(u)-f(v)|\ge 1$. 若一个$L(2,1,1)$-标号中的所有像元素都不超过整数$k$, 则称之为图$G$的$k$-$L(2,1,1)$-标号. 图$G$的$L(2,1,1)$-标号数, 记作$\lambda 2,1,1(G)$,是使得图$G$存在$L(2,1,1)$-标号的最小整数$k$. 本文研究了毛毛虫树的最优$L(2,1,1)$-标号,给出了一些$L(2,1,1)$-标号数达到上界的充分条件,并完全刻画了最大边度为6的毛毛虫树的$L(2,1,1)$-标号数.

英文摘要:

      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$.