最大度为3的树的L(2,1)-标号数的一个刻画  

A Characterization of L(2,1)-Labeling Number for Trees with Maximum Degree 3

作　　者：陈东[1] 邵慰慈[2] 舒巧君[3] 辛百桥 王维凡[4] 

机构地区：[1]浙江师范大学行知学院,金华321004 [2]香港浸会大学数学系 [3]杭州电子科技大学理学院,杭州310018 [4]浙江师范大学数学系,金华321004

出　　处：《数学学报（中文版）》2016年第5期685-710,共26页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(11401535;11371328);国家留学基金资助项目;香港浸会大学教师研究基金资助项目;浙江省自然科学基金资助项目(LQ15A010010)

摘　　要：图G的一个L(2,1)-标号是对G顶点集合的一个非负整数分配,使得其中相邻的点取得的整数差值至少为2并且距离为2的点取得不同的整数.L(2,1)-标号数就是所有这样的标号分配中最小的标号跨度值.Griggs和Yeh的[Labelling graphs with a condition at distance 2,SIAM J.Discrete Math.,1992,5:586-595]已经证明了,一棵树的L(2,1)-标号数不是△就是△+1.对于最大度为3的树的L(2,1)-标号数,本文给出了一个完全的刻画.An L（2, 1）-labeling of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices receive numbers differed by at least 2, and vertices at distance 2 are assigned distinct numbers. The L（2, 1）-labeling number is the minimum range of labels over all such labeling. It was shown by Griggs and Yeh[Labelling graphs with a condition at distance 2, SIAM J. Discrete Math., 1992, 5：586-595] that the L（2,1）-labeling number of a tree is either Δ＋1 or Δ＋2. We give a complete characterization of L（2, 1）-labeling number for trees with maximum degree 3.

关 键 词：L(2 1)-标号 刻画 树 距离2 

分 类 号：O157.5[理学—数学]