图的3-彩虹指标的相关研究

发布时间：2017-08-16 09:03

  本文关键词：图的3-彩虹指标的相关研究

  更多相关文章： 3-彩虹指标 控制集 二部图 图的运算 分裂图

【摘要】：2009年,Chartrand, Okamoto, Zhang提出了k-彩虹连通.令G是一个非平凡的连通图,在G上定义一个边着色c:E(G)→{1,2,...,k},k∈EN图G的一个树是彩虹的,如果这个树上的边分别着不同的颜色.使得对图中任意k个顶点构成的集合S都存在一个连接它的彩虹树T(S (?) V(T))的着色称为是k-彩虹着色,k-彩虹着色中使用的最少的着色数称为k-彩虹指标,记为rxk(G)本文对3-彩虹指标,进行了相关问题研究.全文共分为六个部分.第一部分简单介绍了研究问题的背景与现状,论文的结构和主要结论.第二部分给出了本文所需的概念和符号以及证明中用到的预备知识.第三部分主要研究图的3-彩虹指标的上界.该部分首先借助于图的控制集界定n阶连通图G的3-彩虹指标,并利用它证明了完全二部图KS,t{3≤s≤t)的3-彩虹指标的紧的上界.并且,对其它完全二部图K2,t,南我们使用棋盘法得到3-彩虹指标的精确值.其次,我们得到对于无(P5,C5)且最小度大于等于3的n阶连通图G的上界.另外,利用2-连通图的3-彩虹指标的研究成果,证明了一般图G的3-彩虹指标的上界,且得到了紧的实例.第四部分主要研究图的运算的3-彩虹指标.该部分得到了图的卡式积,字典积,强积,联图,图的顶点分裂和边的收缩运算的3-彩虹指标与对应原图的指标的关系表达式,并且,对于图的卡式积运算,证明了达到上界时的充分条件.第五部分主要探究了分裂图的3-彩虹着色.该部分对于分裂图G,通过一个算法得到了它的几乎最优的3-彩虹着色.此算法是在对分裂图的3-彩虹着色特征分析的基础上,构造出了分裂图的3-彩虹着色,并且证明了该着色使用了rx3(G)+2或rx3(G)+3种颜色.第六部分是本文的结束语,对本文进行了概括性总结和未来的展望.
【关键词】：3-彩虹指标 控制集 二部图 图的运算 分裂图
【学位授予单位】：天津大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要4-5
• Abstract5-8
• 第一章 前言8-13
• 1.1 研究背景与定义8-10
• 1.2 论文结构及主要结论10-13
• 第二章 预备知识13-17
• 2.1 图的基本概念和符号13-15
• 2.2 基本的性质和定理15-17
• 第三章 3-彩虹指标的上界17-27
• 3.1 完全二部图K_(s,t)的3-彩虹指标17-24
• 3.1.1 3≤s≤t的情形17-19
• 3.1.2 2=s≤t的情形19-24
• 3.2 无(P_5,C_5)图的3-彩虹指标的界24-25
• 3.3 一般图的3-彩虹指标的紧的上界25-27
• 第四章 图的运算的3-彩虹指标27-39
• 4.1 卡式积28-32
• 4.2 字典积32-35
• 4.3 其它图的运算35-39
• 第五章 分裂图的3-彩虹着色39-43
• 5.1 算法-分裂图的3-彩虹着色39-40
• 5.2 算法的有效性40-43
• 第六章 结束语43-44
• 参考文献44-47
• 攻读硕士期间所发表论文47-48
• 致谢48

【相似文献】

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

1 贺佩玲;;完全二部图k_(4,n)去掉两条边的交叉数[J];衡阳师范学院学报;2008年06期

2 贺佩玲;罗志军;黄元秋;;几个完全二部图去掉一条边的交叉数[J];河南师范大学学报(自然科学版);2011年02期

3 冯荣权,金珠英;完全二部图乘积上的Graham pebbling猜想[J];中国科学(A辑);2001年03期

4 王建,邱筝;｛P_4,C_4,S_4｝——分解[J];南通职业大学学报(综合版);2001年04期

5 霍美霞;张钦峰;张淑芹;;完全二部图的λ_4-最优性[J];科学技术与工程;2008年07期

6 潘玉美;莫明忠;;完全二部图全着色的构造[J];广西科学院学报;2010年01期

7 杨东;王井玉;;完全二部图的邻接谱(英文)[J];兰州大学学报(自然科学版);2011年03期

8 陈纲;;蕴含K_(3,s)-ke的可图序列[J];广西科学;2006年03期

9 陈祥恩;胡志涛;王治文;;完全二部图K_(1,n),K_(2,n)和K_(3,n)的点强可区别全染色[J];数学的实践与认识;2012年11期

10 胡志涛;王治文;陈祥恩;;完全二部图K_(4,n)的点强可区别全染色[J];西南大学学报(自然科学版);2013年03期

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

1 刘凤霞;完全二部图的单色树划分和单色树覆盖[D];南开大学;2009年

2 范文文;边传递的完全二部图及完全二部地图[D];云南大学;2014年

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

1 傅孟达;完全二部图K_(4,n)所有符号图的准亏格上界[D];湖南科技大学;2015年

2 江妙浩;在一些图上的H-Hopf模结构[D];广西师范学院;2015年

3 臧玉萍;匹配的anti-Ramsey染色[D];浙江师范大学;2016年

4 刘婷婷;图的3-彩虹指标的相关研究[D];天津大学;2015年

5 张颖芳;完全二部图K_（n，n）的循环圈分解及边—平衡指数集[D];河南理工大学;2009年

6 范文文;局部2-弧传递的完全二部图[D];云南大学;2011年

7 孔浩;图的均匀（t，，k，d）-树染色[D];山东大学;2011年

8 龙建军;一些图的[r,s,t]染色[D];福州大学;2011年

9 胡志涛;图的点强可区别全染色的研究[D];西北师范大学;2013年

10 王井玉;若干图的谱性质研究[D];兰州大学;2010年

本文编号：682389