关于图的几类标号问题

发布时间：2017-04-30 02:03

  本文关键词：关于图的几类标号问题，由笔耕文化传播整理发布。

【摘要】：本学位论文所研究的几类标号问题都是源自于无线电频率分配为背景距离2标号问题.图G的一个κ-L(2,1)-标号就是从V(G)到{0,1,…,κ}的一个映射使得相邻的两个顶点取得的值至少相差p,距离为2的两个顶点取得的值至少相差q.图的(d,1)-全标号问题就是L(p,q)-标号问题衍生出来的一种新的标号问题.图G的一个κ-((d,1)-全标号就是从V(G) U E(G)到{0,1,…,κ}的一个函数使得相邻的两个顶点取值不同,相邻的两条边取值不同,相关联的顶点与边取得的值至少相差d.与(2,1)-全标号类似,图G的一个κ-(2,1)-点面标号就是从V(G)∪ F(G)到{0,1,…,κ}的一个映射使得相邻的两个点取值不同,相邻的两个面取值不同,相关联的顶点和面取得的值至少相差2.本学位论文主要围绕这几类标号问题开展研究,共分为四章.第一章,我们给出了图论的一些基本概念与术语,并介绍了L(p,q)-标号问题以及(d,1)-全标号问题的研究背景和研究进展,同时简要罗列了本学位论文的主要研究结果.第二章,我们主要研究了最大度为3的树的L(2,1)-标号数的刻画问题.首先,我们给出了最大度为3的树的一个结构引理.然后,通过我们定义的一个标号过程,把一些含有特定结构的树定义为好的.最后,我们证明了最大度为3的树的L(2,1)-标号数为△+1当且仅当树T是好的.第三章,我们研究了图的(2,1)-全标号问题,得到了两个第一类(即(2,1)-全标号数是△+1)的树的充分条件：(I)对于△4的树T,如果每一个大点至多与△-3个大点相邻,那么T就是第一类的；(Ⅱ)对于△≥9的树T,如果T中不存在两个距离为偶数的坏点,那么T就是第一类的.此外,我们还证明了外平面图的(2,1)-全标号数至多为△+2.第四章,我们介绍了一个新的概念——图的(2,1)-点面标号问题,并针对几个简单图类给出了其(2,1)-点面标号数的紧的上界,如树、圈、欧拉二部图、K4、外平面图等.另外,我们还刻画了至多含有一个闭内面的外平面图的(2,1)-点面标号数.
【关键词】：图 树 L(2 1)-标号 (2 1)-全标号 (2 1)-点面标号
【学位授予单位】：苏州大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-6
• Abstract6-10
• 第一章 绪论10-21
• 1.1 基本概念11-13
• 1.2 两类标号问题的研究背景及其进展13-19
• 1.2.1 L(2,1)-标号问题13-17
• 1.2.2 (2,1)-全标号问题17-19
• 1.3 主要结果19-21
• 第二章 树的L(2,1)-标号21-59
• 2.1 结构引理21-28
• 2.2 最大度为3的树的L(2,1)-标号数的刻画28-59
• 2.2.1 充分性41-54
• 2.2.2 必要性54-59
• 第三章 图的(2,1)-全标号59-103
• 3.1 树的(2,1)-全标号59-81
• 3.1.1 充分条件Ⅰ59-67
• 3.1.2 充分条件Ⅱ67-81
• 3.2 外平面图的(2,1)-全标号81-103
• 3.2.1 △(G)≤3的情况81-83
• 3.2.2 △=4的情况83-100
• 3.2.3 △≥5的情况100-103
• 第四章 图的(2,1)-点面标号103-114
• 4.1 一些简单图类的(2,1)-点面标号103-106
• 4.2 外平面图的(2,1)-点面标号106-114
• 参考文献114-119
• 攻读博士期间完成的论文119-120
• 致谢120-12

【相似文献】

中国期刊全文数据库 前10条

1 王新红;外平面图的L(2,1)-标号[J];数学研究与评论;2003年03期

2 战新刚;一类外平面图的有界染色[J];山东大学学报(理学版);2004年01期

3 陈勇,张少强;一个求外平面图最小反馈点集的多项式时间算法[J];济南大学学报(自然科学版);2004年01期

4 宋慧敏,吴建良;几乎外平面图的边染色[J];山东大学学报(工学版);2004年04期

5 孔立;关于Euler公式的一个应用[J];山东电大学报;2004年04期

6 巩在武,孟宪勇;低度外平面图的点强全染色[J];山东科技大学学报(自然科学版);2004年03期

7 张少强,王骁力,李国君;一个求外平面图最小顶点赋权反馈点集的线性时间算法(英文)[J];数学研究与评论;2004年04期

8 孔立,倪亚洲;双外平面图的边染色[J];山东教育学院学报;2004年06期

9 孔立;双外平面图的边面染色[J];烟台师范学院学报(自然科学版);2005年02期

10 孔立;一个特殊的双外平面图的全染色[J];洛阳大学学报;2005年02期

中国重要会议论文全文数据库 前2条

1 冯纪先;;标定的最大外平面图G_(MO)的数目[A];第十六届电工理论学术年会论文集[C];2004年

2 冯纪先;;最大外平面图G_(MO)的度[A];第十九届电工理论学术年会论文集[C];2007年

中国博士学位论文全文数据库 前1条

1 陈东;关于图的几类标号问题[D];苏州大学;2015年

中国硕士学位论文全文数据库 前10条

1 刘广德;双外平面图的点染色[D];山东大学;2008年

2 孔立;双外平面图的染色问题[D];山东大学;2005年

3 刘维;外平面图的列表着色[D];华中师范大学;2012年

4 单伟;几类图的双约束边染色问题[D];山东大学;2008年

5 许丰伟;图的完全可定向性[D];浙江师范大学;2010年

6 方峻峰;平面图染色问题的研究[D];山东科技大学;2003年

7 邵泽玲;外平面图的松弛竞赛色数[D];河北工业大学;2003年

8 张少君;图的若干特殊正常全染色[D];西北师范大学;2006年

9 柳顺义;若干图类的强边着色[D];西北师范大学;2008年

10 汤宇翔;图的L（d，1）-标号[D];浙江师范大学;2009年

  本文关键词：关于图的几类标号问题，由笔耕文化传播整理发布。

，

本文编号：336002