图的L(d,1)-标号

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:leosky_001
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文所考虑的图都是简单的有限图,给定一个图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)-标号数.
其他文献
本篇博士论文讨论了二阶非线性泛函微分方程、高阶非线性泛函微分方程周期解及同宿轨和异宿轨的存在性。全文共为五章。 第一章为综述,简要回顾泛函微分方程周期解的存在性
本文主要研究了两类问题:广义向量拟平衡问题解的存在性以及广义向量平衡问题解的H(o)lder连续性,具体内容如下:   在Hausdorff向量拓扑空间中,讨论了三类广义向量拟平衡问题(
图的染色问题是图论的主要研究领域之一,是图论研究中很活跃的一个课题,它在组合分析和实际生活中有广泛的应用。随着科技的发展,经典的各类染色已经不能满足要求,于是产生了许多