图的距离边标号及其相关问题

发布时间：2017-11-20 12:31

  本文关键词：图的距离边标号及其相关问题

  更多相关文章： L(j k)-标号 L(j k)-边标号 强边着色 (s t)-放松强边着色 μ-放松强边着色 无穷正则树 轮图 Halin图 项链 六边形网格图 四边形网格图 三角形网格图

【摘要】：设j和k为两个非负整数,图的L(j,k)-标号是一类图的距离着色问题,它是从频道分配问题中抽象出来的着色问题,具有重要的理论价值与应用背景。设m为一个正整数,图G的一个m-L(J,k)-标号,是指用非负整数集{0,1….,m}中的数去对图的顶点进行标号,使得任意相邻的两个顶点到得的标号之差至少为j,任意距离为二的两个顶点得到的标号之差至少为k。实际上,图的L(j,k)-标号就是原图的平方图的距离着色,它进一步拓展了着色理论的实际应用范围。近二十年来,L(j,k)-标号得到了广泛的研究,且研究成果不断涌现。类似图的L(j,k)-标号,可以得到图的L(.j,k)-边标号。图G的一个m-L(j,k)-边标号,是指用非负整数集{0,1...,m}中的数去对图的边进行标号,使得任意相邻的两条边到得的标号之差至少为j,任意距离为二的两条边得到的标号之差至少为k。一个图的所有m-L(j,k)-标号中最小的m称为该图的L(J,k)-边标号数。本文重点研究了一些图类当j=1,k=2时的L(j,k)-边标号数,即L(1,2)-边标号数。图的强边着色,是一种特殊的距离着色,它要求相邻的边得到的颜色不同,距离为二的边得到的颜色也不相同。实际上,图的强边着色也就是图的L(1,1)-边标号。在频道分配过程中,如果频道资源有限,问题就随之而来,即如果在给定的频道数目下,不能得到一个频道分配使之满足距离的约束。这时,就要考虑在频道分配时对距离的约束进行放松。设s和t为两个非负整数,本文提出了(s,t)-放松和β-放松强边着色的定义。图G的一个(s,t)-放松m-强边着色,是指用m个颜色给边集着色,使得对图G的任意一条边,最多有s条e的邻边和t条与e距离为二的边和e的颜色相同。图G的(s,t)-放松强边色数是指使得G存在(s,t)-放松m-强边着色的最小整数m。给定正整数β,如果对任意一条边e,在其邻边和距离为二的边中,最多有μ条边的颜色和e相同,则称之为图G的一个μ-放松m-强边着色。图G的β-放松强边色数是指使得G存在β-放松m-强边着色的最小整数m。本文重点研究了树的(1,0)-放松强边着色、无穷正则树的(s,0)-放松和(0,t)-放松强边着色以及1-放松和2-放松强边着色。本文得到的主要结论概括如下：(1)关于L(1,2)-边标号的研究,主要结论为：确定了路、圈、完全图、完全多部图和轮图的L(1,2)-边标号数；当△=3和4时,确定了无穷△-正则树的L(1,2)-边标号数,当△≥5时,给出了无穷正则树的L(1,2)-边标号数的界；项链Neh是一类特殊的Halin图,当1≤h≤4时,确定了Neh的L(1,2)-边标号数,当h≥5时,给出了Neh的L(1,2)-边标号数的界,并证明了上下界都是可达的；分别给出了六边形、四边形和三角形网格图的L(1,2)-边标号数的界。(2)关于放松强边着色的研究,主要结论为：对一般的树,给出了其(1,0)-放松强边着色数的界,并且证明了上界和下界都是可达的；对无穷正则树,对任意的正整数s和t,确定了(s,0)-放松和(0,t)-放松强边色数,并确定了1-放松和2-放松强边色数。
【学位授予单位】：东南大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】

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

1 王淑栋,庞善臣;系列平行图的边色数[J];山东科技大学学报(自然科学版);2002年02期

2 牟海波;串图的边色数[J];兰州铁道学院学报;2003年03期

3 田双亮;若干n重积图的点可区别边色数[J];西北民族大学学报(自然科学版);2005年02期

4 尹志刚;费旭云;李晓彪;何建新;;关于图的圆边色数几个重要定理[J];高师理科学刊;2011年04期

5 王艳丽;苗连英;;图的集合边色数[J];山东大学学报(理学版);2012年06期

6 贾振声;何满年;张忠辅;;关于图的3—边色数[J];太原重型机械学院学报;1992年01期

7 卓新建;边色数为Δ的一个充分条件[J];曲阜师范大学学报(自然科学版);1995年04期

8 刘二根;广义图K(5,n)的边色数[J];华东交通大学学报;1997年02期

9 田双亮,张忠辅;积图邻强边色数的注记[J];兰州交通大学学报;2005年03期

10 瞿晓鸿;;一个特殊图形的边色数[J];昆明理工大学学报(理工版);2006年02期

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

1 刘华;赵鹏;马明;冶建华;张忠辅;;图S_m*F_n的邻点可区别的边色数[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 包世堂;;关于C_m懔C_n的边色数[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

3 赵传成;;关于C_m·S_n和C_mΔSn的边色数[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

4 马刚;;S_m∨F_n的全色数和点可区别边色数[A];中国运筹学会第九届学术交流会论文集[C];2008年

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

1 贺丹;图的距离边标号及其相关问题[D];东南大学;2015年

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

1 杨海珍;一些图的圆边色数[D];首都师范大学;2008年

2 章文超;图的贪婪博弈边色数和游戏边色数[D];浙江师范大学;2014年

3 毛新叶;图的点可区别边染色的一些结果[D];西北师范大学;2009年

4 刘利群;图的D（2）-点可区别及点可区别正常边染色[D];西北师范大学;2007年

5 田京京;图的D（β）-点可区别边染色及其概率方法[D];西北师范大学;2007年

6 杨玉红;若干图类的星边染色[D];西北师范大学;2009年

7 邓凯;图的星边染色[D];西北师范大学;2007年

8 薄朝升;星着色和强边着色的研究[D];重庆大学;2011年

9 王晓琦;若干合成图的星边染色和星全染色[D];西北民族大学;2013年

10 杨清军;一些特殊图的强边着色和平方自由着色[D];重庆大学;2010年

，

本文编号：1207191