L(s, t) Edge Spans of Trees and Product of Two Paths
Qing-Jie Niu, Wensong Lin, Zengmin Song · Journal of Southeast University · 2007
L(s, t)-labeling is a variation of graph coloring which is motivated by a special kind of the channel assignment problem. Let s and t be any two nonnegative integers. An L (s, t)-labeling of a graph G is an assignment of integers to the vertices of G such that adjacent vertices receive integers which differ by at least s, and vertices that are at distance of two receive integers which differ by at least t. Given an L(s, t)-labeling ƒ of a graph G, the L(s, t) edge span of ƒ, β(subscript st)(G, ƒ)=max{|ƒ(u)-ƒ(v)|: (u, v)∈ E(G)} is defined. The L(s, t) edge span of G, β(subscript st)(G), is minβ(subscript st)(G, ƒ), where the minimum runs over all L(s, t)-labelings ƒ of G. Let T be any tree with a maximum degree of △≥2. It is proved that if 2s≥t≥0, then β(subscript st)(T)=([△/2]-1)t+s; if 0≤2s＜t and △ is even, then β(subscript st) (T)= [(△-1)t/2]; and if 0≤2s＜t and △ is odd, then β(subscript st)(T)=(△-1)t/2+s. Thus, the L(s, t) edge spans of the Cartesian product of two paths and of the square lattice are completely determined.