论文部分内容阅读
本文所考虑的图都是简单的有限图,给定一个图G,我们用V(G),E(G),△(G)分别表示它的顶点集合,边集合和最大度.图G的一个k-L(d,1)-标号是一个从V(G)到标号集合(0,1,…,k)的映射,使得当x和y相邻时有|f(x)-f(y)|≥d,当x和y距离为2时有|f(x)-f(y)|≥1.G的L(d,1)-标号数λd(G)定义为G的所有k-L(d,1)-标号中最小的k值.
图的L(2,1)-标号问题起源于Hale[1]的频道分配问题。这类问题近年来得到广泛研究.1992年,Griggs和Yeh[2]猜想:对于一个△(G)≥2的图G,有λ2(G)≤△2(G).当前最好的结果是λ2(G)≤△2(G)+△(G)-2,由Goncalves[3]给出.
本学位论文在前人的工作基础上继续研究图的L(d,1)-标号问题.在第一章中,我们给出概念以及图的L(d,1)-标号问题的研究背景和现状,并且介绍了本学位论文的主要结果.
在本文的第二,三,四,五章中,我们分别考虑了2-外平面图的L(2,1)-标号,广义Petersen图,平而格子点图和三角格子点图的L(d,1)-标号问题.我们的主要结果如下:
(1)对于任意的2-外平面图G,λ2(G)≤△(G)+12.
(2)对于任意的广义Petersen图P(n),若d≥3且n≥3,则λd(P(n))≤3d+3.
(3)确定了平面格子点图和三角格子点图的L(d,1)-标号数.