【摘要】：标号着色是从频道分配问题中抽象出来的一种图着色概念。与经典的图着色相比,它不仅要求图中相邻元素的着色有着明显的差别,同时还要求图中不相邻元素的着色有所不同。图G的距离二标号着色也即L(j,k)-标号,有整数距离二标号(j,k为非负整数)和实数距离二标号(j,k为非负实数)两种模式。它们分别是定义在V(G)→{0,1,2,3,…}和V(G)→[0,+∞)上的函数f,满足条件：(1)|f(u)-f(v)|≥j,若uv∈E(G)；(2) |f(u)-f(v)|≥k,若d(u,v)=2。图G的L(j,k)-标号着色数λj,k(G)=minf max{f(v): v∈V(G)}。随着图着色问题研究的不断深入,各种各样的图着色的变形和推广出现并被广泛研究,诸如有缺陷着色、非正常着色、荫度等等,它们都可看作是对图的正常着色的放松。着色放松问题实际上还有很多问题值得深入挖掘和思考。标号着色的放松问题在理论上就值得研究,同时它也有实际应用价值。为解决频道分配问题,需要选取合适的数学模型,合理地分配稀缺并且有限的频道资源。放松的距离二标号着色是更为合适的频道分配问题的数学模型。假设G是一个图,f：V(G)→{0,1,2，...]是一个映射,s,t是两个非负整数。若对于G的任何两个相邻顶点u,v,f(u)≠f(v)；对于G的任何顶点u,至多有s个u的邻点标号属于集合{f(u)-1,(u)+1},至多有t个u的2-邻点的标号等于f(u),则称f是图G的(s,t)-放松的L(2,1)-标号。记f的跨度为span(f),表示图中顶点的最大标号和最小标号的差。图的(s,t)-放松的L(2,1)-标号的最小跨度定义为图的(s,t)-放松的L(2,1)-标号着色数,记为λ2,1s,t(G)。图的(s,t)-放松的L(2,1)-标号是对图的整数L(2,1)-标号作出相应的放松而产生的新的图标号概念。假设G是一个图,f：V(G)→[0,+∞)是一个映射,s,t是两个非负整数,j,k是实数并且jk≥1。若对于任一顶点u,至多s个u的邻点标号属于(f(u)-j,f(u)-k]∪ [f(u)+k,f(u)+j),其他邻点的标号属于[0,f(u)-j]∪[f(u)+j,+∞)；至多t个u的2-邻点的标号属于(f(u)-k,f(u)+k),u的其他2-邻点的标号属于[0,f(u)-k]∪[f(u)+k,+∞),则称f是图G的(s,t)-放松的L(j,k)-标号。图的(s,t)-放松的L(j,k)-标号着色的最小跨度定义为图的(s,t)-放松的L(j,k)-标号着色数,记为λj,ks,t(G)。图的(s,t)-放松的L(j,k)-标号这一概念是通过对图的实数L(j,k)-标号作出相应的放松而产生的。若d＝j/k,则λj,ks,t(G)=kλd,1s,t(G)。图的(s,t)-放松的L(j,k)-标号和图的(s,t)-放松的L(d，，1)-标号可以相互转化。网格图(六边形网格图、四边形网格图以及三角形网格图)是频道分配问题中干扰图的理想模型。本文主要考虑各种网格图的(s,t)-放松的L(2,1)-标号着色以及(s,t)-放松的L(d,1)-标号着色问题,研究并得出了它们的一些基本性质,讨论了它们的所有可能的(s,t)-放松的情形。确定了三种网格图的所有s,t情形下的(s,t)-放松的L(2,1)-标号着色数,确定了六边形网格图的所有s,t和任意d1情形下的(s,t)-放松的L(d,1)-标号着色数,确定了四边形网格图的几乎所有s,t和任意d1情形下的(s,t)-放松的L(d,1)-标号着色数(除了s＝0,t＝1,1d2这一情形以外),确定了三角形网格图的大多数情形下的(s,t)-放松的L(d,1)-标号着色数以及其余情形下的(s,t)-放松的L(d,1)-标号着色数的界。这些结果给相应的频道分配问题提供了一系列的频道分配方案。
【学位授予单位】：东南大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【相似文献】
相关期刊论文 前10条
1 卢建立;任凤霞;马美琳;;中间图的邻点强可区别全染色[J];河南师范大学学报(自然科学版);2012年05期
2 马生全,张忠辅,姚兵,李敬文;C_(3n)~2,C_(4n)~2邻点可区别的全染色[J];兰州铁道学院学报;2003年04期
3 李敬文;强会英;张忠辅;王文杰;王治文;;高度图的邻点可区别的全染色界的一点注[J];兰州交通大学学报;2006年01期
4 王颜妮;王丽伟;刘萍;;几类图的邻点可区别的全染色[J];科学技术与工程;2007年13期
5 王雅琴;刘西奎;王英;;一些图的邻点可区别关联着色[J];大学数学;2008年04期
6 刘海涛;;C_(5m)×C_(5n)图的邻点可区别的边染色[J];河西学院学报;2008年02期
7 卞西燕;苗连英;尚华辉;段春燕;马国翼;;图的邻点可区别边划分(英文)[J];华东师范大学学报(自然科学版);2009年04期
8 郑纯;刘焕平;;扇和轮的邻点强可区别全染色[J];哈尔滨师范大学自然科学学报;2009年05期
9 严谦泰;;k-方图的一般邻点可区别边染色[J];安徽大学学报(自然科学版);2010年03期
10 严谦泰;严楷;;关于图的一般邻点可区别边染色[J];数学的实践与认识;2010年24期
相关会议论文 前3条
1 李莉;耿显民;;一类随机图的邻点度数和[A];第十一届中国不确定系统年会、第十五届中国青年信息与管理学者大会论文集[C];2013年
2 曹渊;郭永辉;王铁良;田宙;;自然邻点插值方法在材料状态方程数据库开发中的应用[A];中国计算力学大会'2010（CCCM2010）暨第八届南方计算力学学术会议（SCCM8）论文集[C];2010年
3 刘君;赵传成;任志国;包世堂;李敬文;张忠辅;;C_m·F_n的邻点可区别的边染色[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年
相关博士学位论文 前3条
1 戴本球;图的放松的距离二标号着色[D];东南大学;2015年
2 孔海荣;区组长为4的二维不含邻点的平衡样本设计[D];河北师范大学;2008年
3 黄丹君;平面图的邻点可区别染色与点荫度[D];苏州大学;2012年
相关硕士学位论文 前10条
1 马瑞琼;复杂网络中社团发现算法的研究[D];电子科技大学;2015年
2 焉秋瑶;图的广义字典积与半强积的邻点可区别和点可区别染色[D];西北民族大学;2015年
3 张彩霞;几类图的邻点可区别均匀E-全染色[D];兰州交通大学;2015年
4 王立丽;关于几类图的Smarandachely邻点全染色[D];兰州交通大学;2015年
5 黄晨悦;一类区组长为5的一维不含邻点的平衡样本设计的存在性[D];河北师范大学;2016年
6 李晓丽;区组长为5的二维不含邻点的平衡样本设计[D];河北师范大学;2016年
7 张晓望;平面图的边染色问题[D];山东大学;2016年
8 聂静方;平面图的非正常染色[D];浙江师范大学;2016年
9 李晓艳;平面图的列表染色[D];浙江师范大学;2016年
10 魏邦魁;若干图的邻点强可区别的E-全染色[D];兰州交通大学;2016年
本文编号：
2547248
