网格图的多重L(2,1)-标号

来源 :东南大学 | 被引量 : 0次 | 上传用户:xiangwang111
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的L(2,1)-标号是从频道分配问题中概括出来的一类图的着色问题,近些年来L(2,1)-标号问题的研究取得了很多成果,L(2,1)-标号概念也被大大推广了。我们考虑如下复杂一些的频道分配模型,进而引出我们的问题。设n和d是正整数,如果某个区域有多个电台,每个电台要发射n个不同的电波信号,为避免干扰,任意两个位置非常接近的信号至少要相距d个频率,而位置比较接近的信号只要频率不同就可以了。用标号的思想来考虑这个问题,就可以把它看成是图的n重L(d,1)-标号。定义任意两个整数集合I和J之间的距离为d(I,J)=min[|i-j|:i∈,I,j∈J}。对于一个给定的图G,它的n重L(d,1)-标号是一个非负整数集函数f:V(G)→非负整数集的所有n子集合的集合,f满足两个条件: (1)d(f(u),f(v))≥d,若uv∈E(G); (2)d(f(u),f(v))≥1,若u与v的距离为2。 图G的n重L(d,1)-标号数定义为λnd,1(G)=minfmaxf(v1)∪f(v2)∪…∪f(vn),其中f取遍图G的所有n重L(d,1)-标号。用同样的正多边形去覆盖平面,仅仅正三角形,正六边形,正方形三种网格图是可行的,在第二部分,我们研究三种网格图:正三角形网格,正六边形网格及多维方形网格的n重L(d,1)-标号和n重L(d,1)-圆标号。通过分析论证和对网格图的顶点循环地分配标号集,我们得到了n重L(d,1)-标号数和n重L(d,1)-圆标号数的取值上下界,特别当d=2时,我们完全确定出三种网格的n重L(d,1)-标号数和n重L(d,1)-圆标号数。 在本文第三部分,我们进一步研究了图G的n重d-分离L(d,1)-标号。用Kn表示n个点的完全图,图G的n重d-分离L(d,1)-标号就是复合图G[Kn]的L(d,1)-标号,而图G的n重L(d,1)-标号等价于G[Kcn]的L(d,1)-标号。当d=2时,我们得到了正三角形网格的n重2-分离L(2,1)-标号数取值范围,并且完全确定了正六边形网格与多维方形网格的的n重2-分离L(2,1)-标号数。
其他文献
Lyapunov矩阵方程和Riccati矩阵方程等线性和非线性矩阵方程是数值代数和非线性分析中研究和探讨的重要课题之一.它们在控制理论,运输理论,动态规划,梯形网络,统计过滤和统计
近年来,国内外学者围绕系统模糊可靠性的研究做了许多工作,发表了一系列研究成果。根据系统信息形式和人对可靠性概念的理解,系统模糊可靠性的研究方法大致被分成五种类型,其
[目的]评价关节镜下微骨折技术结合术后十一方药酒外涂治疗膝关节软骨损伤的临床疗效.[方法]对2007年1月~2010年12月的38例Outerbridge分型Ⅲ~Ⅳ股骨髁及滑车区域的软骨缺损患
Web服务的研究涉及诸多热点问题,如Web服务发现、Web服务自动组合、Web服务组合验证、Web服务组合执行等,这些问题共同构成了Web服务研究的框架。若干单独Web服务按一定方式
研究黎曼流形上的非光滑问题及其相关的问题一直是优化热点问题之一,一些学者把几种重要的非光滑分析工具从欧氏空间推广到了黎曼流形上。本文创新性的在黎曼流形上给出Lipsc
系统的可靠性,也即容错性,是指当互联网络中部分处理器或通信链路发生故障时,系统仍然能够正常、有效地运行,即指当系统中的故障处理器或通信链路被隔离之后,系统仍然保持连通性。
模糊数学在工程技术、管理科学、金融工程等领域应用中的很多问题都可以用模糊方程和模糊线性系统来描述。但是,实现模糊方程和模糊线性系统的求解十分困难,对求解方法的研究
一个偶然的机会,我发现王洛宾1958年在彭德怀部队著名的骑兵“钢铁二连”有过一段特殊的战事经历,这是过去的史料从未涉及过的。为此,我远涉天水市,在甘肃省第三监狱找到了那
网络控制系统是一个具有很强实际应用背景的研究领域,在研究过程中所面临的问题是多种多样的。在网络控制系统的分析与设计中,稳定性是系统的一种结构特性,关系到系统能否正常工
渝糯930是重庆市农业科学院以Y407为母本、DN830为父本组配而成的糯玉米新品种。该品种具有品质优、产量高、适应广、综合抗性好等优点,适宜在江苏中南部、浙江、福建、广东