关于图的L(d,1)-标号问题

• 作者: 刘家壮 邵振东
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: L(2,1)-标号 T-染色 平面三角剖分图 立体四面体剖分图 平面近四边形剖分图
• 年，卷（期）: 2004,（z1）
• 页码范围: 561-566
• 页数: 6页
• 分类号: O157.5
• 字数: 4031字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2004.z1.008

摘要

图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.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邵振东	哈尔滨工业大学深圳研究生院	12	18	3.0	3.0
3	刘家壮	山东大学数学研究所	55	329	10.0	15.0