On EDGE-Labeling With Distance Of Graphs And Some Related Problems

Let j and k be two nonnegative integers. The L(j, k)-labeling of a graph, which was motivated by the frequency assignment problem, is a kind of generalized distance coloring of a graph. Because of its theoretical significance and application background, it is a popular re-search problem in many research fields. Let m be a nonnegative integer. An m-L(j, k)-labeling of graph G is an assignment on the vertices to the set{0,1,2,...,m}, such that adjacent ver-tices receive labels which differ by at least j, and vertices that are distance two apart receive labels which differ by at least k. Actually, L(j, k)-labeling of a graph is a vertex distance coloring of its square graph, and it further expanded the scope of the practical applications of graph coloring theory. In the past 20 years, L(j, k)-labeling has been widely investigated and many papers about distance coloring have been published.Similar to L(j,k)-labeling, one can define L(j, k)-edge-labeling. An m-L(j, k)-edge-labeling of graph G is an assignment on the edges to the set{0,1,2,..., m}, such that adjacent edges receive labels which differ by at least j, and edges that are distance two apart receive labels which differ by at least k. The L(j,k)-edge-labeling number of G is the minimum m such that G has an m-L(j,k)-edge-labeling. In this thesis, the L(1,2)-edge-labelings, which is the case of j=1 and k = 2, of several kinds of graph are investigated.Strong edge coloring is a kind of distance coloring, which demands that the adjacent edges must receive distinct colors and edges at distance two must also receive distinct colors. However, problems may be arisen if the channel resource is limited in a frequency assignment problem. That is to say, it is possible that with given channel number, one cannot construct a good strong edge-coloring. In this case, some kind of relaxation is necessary in assigning channels to transmitters. Let a and t be two nonnegative integers, (s, t)-relaxed and μ-relaxed strong edge coloring are introduced. An (s,t)-relaxed strong m-edge-coloring is an assignment of m colors to the edges of G, such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e assigned the same color as e. The (s, t)-relaxed strong chromatic index is the minimum number m which G has an (s, t)-relaxed strong m-edge-coloring. Let μ be a nonnegative integer, if there are at most μ edges in the adjacent edges and distance two edges of e assigned the same color as e, then the coloring is called μ-relaxed strong m-edge-coloring. And the μ -relaxed strong chromatic index is the minimum number m which G has an μ-relaxed strong m-edge-coloring. In this article, the (1,0)-relaxed strong chromatic indices of trees, the (s,0)-relaxed and (0,t)-relaxed strong chromatic indices of infinite regular trees, the 1-relaxed and 2-relaxed strong chromatic indices of infinite regular trees are investigated.The main results are summarized as follows:(1) The L(1,2)-edge-coloring. The L(1,2)-edge-labeling number of paths, cycles, complete graphs, complete multipartite graphs are determined. When A= 3 and 4, the L(1,2)-edge-labeling number of infinite regular trees are determined, and when A> 5, the bounds of the L(1,2)-edge-labeling number for infinite regular trees are given. Necklace Neh is a kind of Halin graph, when 1≤h≤4, the L(1,2)-edge-labeling numbers of Neh are determined, when h≥4, the bounds of the L(1,2)-edge-labeling number for Neh are given and the bounds are attainable. The bounds of the L(1,2)-edge-labeling number for the hexagonal lattice, the square lattice and the triangular lattice are given.(2) The relaxed strong edge coloring. For general tree, the bounds of (1,0)-relaxed strong chromatic index are given, and it is proven that the bounds are attainable. For infinite regular trees, the (s,0)-relaxed and (0, t)-relaxed strong chromatic indices are determined for all posi-tive integers s and t. The 1-relaxed and 2-relaxed strong chromatic indices of infinite regular trees are determined.