低最大度的平面图的（2,1）-全标号

论文摘要

图论最早起源于18世纪三十年代.Euler在1736年解决了柯尼斯堡七桥问题,由此图论诞生.伴随着图论的兴起和发展,这门新兴的学科,逐渐在化学、信息论、生物学、网络理论、控制论、博弈论及计算机科学领域产生了广泛的应用.图染色问题作为图论最经典的问题之一更是受到了广泛关注.由著名的四色猜想开始,先后产生了点染色、边染色、全染色、列表染色、频道染色等一系列新的研究方向,在现实生活中染色理论有着广泛的应用背景.本文所考虑的图都是连通的简单有限图.如果图G能够嵌入到平面上使得G中的边仅在端点处相交,则称G为平面图或可平面图.通常情况下,V（G）,E（G）分别表示一个图G的顶点集合和边集合.|V（G）|、|E（G）|分别表示图G的顶点数和边数.如果V’ c V,E’（?）E,称G’=（V’,E’）是G=（V,E）的子图,并记作G’（?）G;我们常用添加或删除一些顶点和边的方法来构造一类新图.若V’（?）V（G）,则G-V’是在G中删除V’中的点和与它们关联的所有边而得到的子图.若E’（?）E（G）,则G-E是在G中删除E’中的边而得到的子图.图G中一个顶点u的度是指G中与u相关联的边的数目,记作dG（v）或d（v）.用δ（G）,△（G）分别记作图G的最小度和最大度.面f的度d（f）是指与面f相关联的边的数目.频道分配问题实质上是一个如何分配无线电频道资源以实现最合理应用的最优化问题.在频道分配问题中,为避免传输信号之间的干扰,若两个站点距离非常近,则它们的频率至少相差2;若两个站点稍近,则只需分配不同频率即可.受此问题的启发,Griggs和Yeh[10]引入了 L（2,1）-标号并且很快被推广到L（p,q）-标号的形式.图G的一个L（p,q）-标号是从V（G）到所有非负整数的一个映射φ,使得如果点;x和y相邻,那么|φ（x）-φ（y）|≥ p;如果点x和y距离为2,那么|φ（x）-m（y）|≥ q.图的关联图是指将图G中的每条边都用一条长为2的路代替所形成的新图.Havet[6,7]将一个图的关联图的L（p,1）-标号问题定义为图的（p,1）-全标号问题.该问题也可以被看作是全染色问题的一种推广形式.图G有一个k-（p,1）-全标号当且仅当存在一个将V（G）∪E（G）映射到颜色集合{0,1,2,...,k})的函数f满足:（1）若边uv ∈ E（G）,|f（u）-f（v）|≥1;（2）若边e1和e2在G中相邻,则|f（e1）-f（e2）|≥ 1;（3）若顶点u和边e相关联,则|f（u）-f（e）| ≥ p.使得G可k-（p,1）-全标号的最小的正整数k称为是图G的（p,1）-全标号数,并记作λpT（G）.Havet和Yu[8]提出了如下的（p,1）-全标号猜想:猜想1.3.3[6,8]G是一个最大度为△的平面图,则有λpT（G）≤△+2p-1或λpT（G）≤min{△+2p-1,2△+p-1}.关于图G的（p,1）-全标号数和（2,1）-全标号数的重要的研究结果如下.定理 1.3.4[1]G 是任意一个简单图,则max{r（χ（G）-1）+1,s（λ’（G）-1）+1,t+1}≤Xr,s,t（G）≤r（X（G）-1）+s（χ’（G）-1）+t+1.定理1.3.10[19]令G是一个最大度为△的可平面图,整数p满足p≥2.若G满足△ ≥ 4p+4,则有 λpT（G）≤ △+2p-2.定理1.3.13[22]若G是一个最大度△ ≥ 12的平面图,则△+l ≤ λ2T（G）≤ △+2.定理1.3.14[23]若G是一个最大度△ ≥ 9的平面图.若G中不含长为k的圈,k∈{3,4,5,6},则有 λ2T（G）≤ △+2.本文主要讨论平面图的（2,1）-全标号数.第二章是本论文的重点部分,我们给出了 △（G）=11,10,9的带有限定条件的平面图的（2,1）-全标号数及其证明.第三章我们给出了 △=8,7.6的带有限定条件的平面图的（2,1）-全标号数并且还给出了使用四色定理和不使用四色定理两种不同的证明.本文我们主要得到了如下结论:定理2.1.1若G为平面图,△（G）=11且G中3-圈不与k-圈相邻,k∈{3,4},则 λ2T（G）≤ △+2.定理2.1.2若G为平面图,△（G）=10且G中3-圈不与k-圈相邻,k ∈ {3,4},则（G）≤△+2.定理2.1.3 若G为平面图.△（G）=9且G中3-圈不与k-圈相邻,∈{3,4,5},则 λ2T（G）≤△+2.定理3.2.1 若G为平面图,△（G）=p+5且G不包含5-圈和6-圈,则λ2T（G）<△+5,p1,2,3.

论文目录

文章来源

类型: 硕士论文

作者: 吕萧

导师: 孙磊

关键词: 全标号,平面图,权转移

来源: 山东师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东师范大学

分类号: O157.5

DOI: 10.27280/d.cnki.gsdsu.2019.000056

总页数: 47

文件大小: 2310K

下载量: 8

相关论文文献

• [1].3×n方格染色问题的两个新结果[J]. 数学通报 2011(12)
• [2].一道高考染色问题的创新解法及推广[J]. 中学数学研究 2019(04)
• [3].染色问题的相互转换探究[J]. 福建中学数学 2009(05)
• [4].关于2×n方格的染色问题研究[J]. 中学数学研究 2011(01)
• [5].从染色问题谈两个计数原理的教学[J]. 中学数学 2008(21)
• [6].一道染色问题的妙解[J]. 上海中学数学 2008(01)
• [7].对一类环形染色问题的探究[J]. 中学数学研究 2017(02)
• [8].“无心”和“有心”染色问题[J]. 数学学习与研究 2015(11)
• [9].例谈区域染色问题[J]. 数理化解题研究 2018(07)
• [10].染色问题解题探究[J]. 中学生数理化(学习研究) 2017(07)
• [11].染色问题[J]. 数学大世界(小学五六年级适用) 2013(04)
• [12].两次捆绑快速解决有关染色问题[J]. 中学教学参考 2009(26)
• [13].染色问题解题策略例说[J]. 青苹果 2009(06)
• [14].圆环染色问题的公式解法[J]. 中学生数学 2009(09)
• [15].快速学会对染色问题的彻底处理[J]. 中学生数理化(教与学) 2011(10)
• [16].一类环状染色问题的求解与变式应用[J]. 高中数学教与学 2018(17)
• [17].利用数列递推关系巧解染色问题[J]. 中学数学研究 2010(05)
• [18].计数中一类染色问题的探讨[J]. 中小学数学(高中版) 2015(06)
• [19].高考中一类染色问题的推广与应用[J]. 数学爱好者(高考版) 2008(12)
• [20].通过“染色问题”,培养中学生化归思维[J]. 阴山学刊(自然科学版) 2014(04)
• [21].项链的若干染色问题[J]. 科技导报 2012(07)
• [22].排列组合中的染色问题[J]. 青海教育 2008(04)
• [23].环形染色问题的公式解法[J]. 中学数学杂志 2008(09)
• [24].关于排列组合中染色问题的一种通用解法的研究[J]. 考试(高考数学版) 2012(09)
• [25].关于图的染色问题算法的新研究[J]. 山东轻工业学院学报(自然科学版) 2008(03)
• [26].突破染色问题[J]. 中学生数理化(高三) 2016(03)
• [27].正棱台柱图的染色问题[J]. 阴山学刊(自然科学) 2013(02)
• [28].项链染色问题探讨[J]. 新疆教育学院学报 2012(03)
• [29].排列组合中的染色问题[J]. 科技信息 2011(10)
• [30].染色问题的解法示例[J]. 中学生数理化(高考版) 2011(01)

标签：全标号论文;  平面图论文;  权转移论文;