Relaxed Distance Two Labelings Of Graphs

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.