【作者】 戴本球；

【导师】 林文松；

【作者基本信息】 东南大学 ， 应用数学， 2015， 博士

【摘要】 标号着色是从频道分配问题中抽象出来的一种图着色概念。与经典的图着色相比,它不仅要求图中相邻元素的着色有着明显的差别,同时还要求图中不相邻元素的着色有所不同。图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是实数并且j>k≥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和任意d>1情形下的(s,t)-放松的L(d,1)-标号着色数,确定了四边形网格图的几乎所有s,t和任意d>1情形下的(s,t)-放松的L(d,1)-标号着色数(除了s＝0,t＝1,1<d<2这一情形以外),确定了三角形网格图的大多数情形下的(s,t)-放松的L(d,1)-标号着色数以及其余情形下的(s,t)-放松的L(d,1)-标号着色数的界。这些结果给相应的频道分配问题提供了一系列的频道分配方案。更多还原

【Abstract】 Graph labeling arose from the channel assignment problem as a new graph coloring con-cept. Comparing with the classic colorings, it demands not only the colors of adjacent elements on graph be evidently different, but also the nonadjacent elements of graph be slightly different. There are two kinds of models about distance two labeling, i.e., L(j, k)-labeling of graph G, one is integer distance two labeling for nonnegative integers j and k, the other is real distance two labeling for nonnegative real numbers j and k. They are function f:V(G)→{0,1,2…} or V(G)→ [0,+∞) respectively such that (1)|f(u)-f(v)|≥j, if uv ∈ E(G), and (2) |f(u)-f(v)|≥k, if d{u, v)= 2. The L(j,k)-labeling number of G is denoted by λj,k(G), and λj,k(G)= minf max{f(v):v ∈V(G)}.With the continuously and deeply study made in the problem of graph coloring, various deformation and generalization of graph coloring appear and have been studied extensively, such as defective coloring, improper coloring, arboricity and so on. They can be seen as the relaxation of the proper graph coloring. Many problems about relaxation of graph coloring are worth digging and thinking deeply. The coloring relaxation problem of graph labeling is worth studying in theory, and it also has practical application value. To solve the channel assignment problem, it is necessary to select the appropriate mathematical model, reasonably allocate scarce and limited channel resources. The relaxation of the distance two labeling is a more appropriate mathematical model of channel assignment problem.Suppose G is a graph. Let f denote the function:V(G)→{0,1,2…},s and t be two nonnegative integers. If f(u)≠f(v) for any two adjacent vertices u and v of graph G:and if at most s neighbors of u receive labels from {f(u) - 1,f(u)+1}, and if at most t 2-neighbor labels of u are f(u), then f is called an (s, t)-relaxed L(2, 1)-labeling of G. The minimum span of (s,t)-relaxed L(2, 1)-labelings of G is called the (s, t)-relaxed L(2, 1)-labeling number of G, denoted by λ2,1s,t(G). By making corresponding relaxation on the integer L(2, 1)-labeling, the new graph labeling concept, (s, t)-relaxed L(2, 1)-labeling of graph is generated.Suppose G is a graph. Let f denote the function:V(G)→[0,+∞), s and t be two nonnegative integers, j and k be two real numbers and j> k≥ 1. For any vertex u, if at most s neighbors of u receive labels from (f(u)-j, f(u)-k] U [f(u)+j, f(u)+k), the other neighbors of u receive labels from [0, f(u)-j] ∪ [f(u)+j,+∞), and if at most t 2-neighbors of u receive labels from (f(u)-k,f(u)+k), the other 2-neighbors of u receive labels from [0,f(u)-k] ∪ [f(u)+k,+∞), then f is called an (s, t)-relaxed L(j, k)-labeling of G. The minimum span of (s, t)-relaxed L(j, k)-labelings of G is called the (s, t)-relaxed L(j, k)-labeling number of G, denoted by λj,ks,t(G). The concept of (s, t)-relaxed L(j,k)-labeling of graph is generated by making corresponding relaxation on the real L(j, k)-labeling.If d=j/k, then λj,ks,t(G)= kλd,1s,t(G).The two graph labeling, (s, t)-relaxed L(j, k)-labeling and (s, t)-relaxed L{d, 1)-labeling, can be transformed into each other. Grid graphs such as hexagonal lattice, square lattice and triangular lattice, are ideal models for the interference graphs in the channel assignment problem. This dissertation investigates the problems of (s, t)-relaxed L(2, 1)-labeling and (s, t)-relaxed L(d, 1)-labeling of several lattices. Some basic properties of them are obtained. All possible (s,t)-relaxed cases are discussed. The (s,t)-relaxed L(2, 1)-labeling numbers of these three lattices are determined completely for each pair of two nonnegative integers s and t. For each pair of two nonnegative integers s and t and any real number d which is greater than one, the (s, t)-relaxed L(d, 1)-labeling numbers of hexagonal lattice are determined completely, the (s,t)-relaxed L(d, l)-labeling numbers of square lattice are almost determined completely (except for the case s=0, t=1, and 1< d< 2 ). The (s, t)-relaxed L(d, 1)-labeling numbers of triangular lattice are determined for most cases about the two nonnegative integers s and t and real number d, and are bounded for the rest cases. And this provides a series of channel assignment schemes for the corresponding channel assignment problem.更多还原