The T-colorings And T-edge Spans Of Graphs

T-colorings were introduced by Hale[l] with the channel assignment problem in communications. Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integers f(x) to each vertex xofG such that \f(x) - f(y)\ ?T whenever xy € E(G). T-edge span of G is the minimum value of the edge span of a T-coloring of G.The spectrum of radio and television frequencies is becoming increasingly crowded. This implies that it will be more and more necessary to make channel assignments efficiently. So as to conserve spectrum, one criteria T-edge span is important for measuring the efficiency.Since Hale[l] formulated the channel assignment problem graph-theoretically, plenty of research work and exploration have been done on this field. The notion of T-coloring has given rise to a large literature, but a considerable number of unsolved problem have been remained open. Comparing to T-spans, there are relatively fewer known results about T-edge spans of graphs. In this paper, firstly we systematically summarize the main results and development on T-coloring in recent years, then we investigate the article of Shin- Jie Hu[2] thoroughly which studies the T-edge span of the dth power Cdn of the n-cycle Cn for T = {0,1,2,... k - 1}. On the base of it, we successfully define a T-coloring / by dividing the vertex n into m periods, then we prove that / is a T-coloring of the graph C^ and espr???. At that tune we also prove espr?? by giving two new definitions. The results improves the preceding theorem in that article, omitting the condition of the gcd(n,d + 1) = 1, we obtain a better upper bound, on the other hand, we obtain another better lower bound. Which make this results more generalized and perfect. The solving of this problem will make the channel assignment more efficient.