张小玲.毛毛虫树的最优$L(2,1,1)$-标号[J].数学研究及应用,2023,43(2):150~160
毛毛虫树的最优$L(2,1,1)$-标号
Optimal $L(2,1,1)$-Labelings of Caterpillars
投稿时间:2022-02-24  修订日期:2022-05-21
DOI:10.3770/j.issn:2095-2651.2023.02.003
中文关键词:  频率分配  $L(2,1,1)$-标号  标号数  毛毛虫树
英文关键词:channel assignment  $L(2,1,1)$-labeling  span  caterpillar
基金项目:国家自然科学基金青年科学基金(Grant No.11601265), 集美大学科研启动项目(Grant No.Q202201).
作者单位
张小玲 集美大学师范学院, 福建 厦门 361021 
摘要点击次数: 271
全文下载次数: 239
中文摘要:
      图$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$.
查看全文  查看/发表评论  下载PDF阅读器