关于几类图的L(2,1)标号问题

• 作者: 刘家壮 邵振东
• 来源期刊: 应用数学
• 学科: 数学
• 关键词: L(2,1)-标号 Kneser图 Mycielski图 Descartes图 Halin图
• 年，卷（期）: 2004,（1）
• 页码范围: 31-36
• 页数: 6页
• 分类号: O157.5
• 字数: 2192字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9847.2004.01.006

摘要

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则 |f(x)-f(y)|≥2;若d(x,y)=2,则 |f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v):v∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文给出了Kneser图,Mycieklski图,Descartes图,Halin图的λ值的上界,并证明了上述猜想对以上几类图成立.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邵振东	南京大学数学系	12	18	3.0	3.0
2	刘家壮	山东大学数学研究所	55	329	10.0	15.0