Hits :

First Author : 陈东

Affiliation of Author(s): 数理与信息工程学院

Date of Publication : 2016-01-01

Document Type : 期刊

Journal : 数学学报

Volume: 第59卷

Issue : 第5期

Page Number : 685-710

ISSN : 0583-1431

Translation or Not : no

Key Words : L(2,1)-标号；刻画；树；距离2

Abstract : 图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)-标号数,本文给出了一个完全的刻