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 assig...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 f of a graph G, the L（s, t） edge span of f, βst （ G, f） = max { ｜f（u） -f（v）｜： （ u, v） ∈ E（G） } is defined. The L（ s, t） edge span of G, βst（G）, is minβst（G,f）, where the minimum runs over all L（s, t）-labelings f of G. Let T be any tree with a maximum degree of △≥2. It is proved that if 2s≥t≥0, then βst（T） =（ [△/2 ] - 1）t ＋s; if 0≤2s 〈 t and △ is even, then βst（T） = [ （△ - 1） t/2 ] ; and if 0 ≤2s 〈 t and △ is odd, then β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.展开更多
Given a graph G and a positive integer d, an L( d, 1) -labeling of G is afunction / that assigns to each vertex of G a non-negative integer such that |f(u)-f (v) | >=d ifd_c(u, v) =1;|f(u)-f(v) | >=1 if d_c(u, v...Given a graph G and a positive integer d, an L( d, 1) -labeling of G is afunction / that assigns to each vertex of G a non-negative integer such that |f(u)-f (v) | >=d ifd_c(u, v) =1;|f(u)-f(v) | >=1 if d_c(u, v) =2. The L(d, 1)-labeling number of G, lambda_d(G) is theminimum range span of labels over all such labelings, which is motivated by the channel assignmentproblem. We consider the question of finding the minimum edge span beta_d( G) of this labeling.Several classes of graphs such as cycles, trees, complete k-partite graphs, chordal graphs includingtriangular lattice and square lattice which are important to a telecommunication problem arestudied, and exact values are given.展开更多
基金The National Natural Science Foundation of China(No10671033)Southeast University Science Foundation ( NoXJ0607230)
文摘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 f of a graph G, the L（s, t） edge span of f, βst （ G, f） = max { ｜f（u） -f（v）｜： （ u, v） ∈ E（G） } is defined. The L（ s, t） edge span of G, βst（G）, is minβst（G,f）, where the minimum runs over all L（s, t）-labelings f of G. Let T be any tree with a maximum degree of △≥2. It is proved that if 2s≥t≥0, then βst（T） =（ [△/2 ] - 1）t ＋s; if 0≤2s 〈 t and △ is even, then βst（T） = [ （△ - 1） t/2 ] ; and if 0 ≤2s 〈 t and △ is odd, then β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.
文摘Given a graph G and a positive integer d, an L( d, 1) -labeling of G is afunction / that assigns to each vertex of G a non-negative integer such that |f(u)-f (v) | >=d ifd_c(u, v) =1;|f(u)-f(v) | >=1 if d_c(u, v) =2. The L(d, 1)-labeling number of G, lambda_d(G) is theminimum range span of labels over all such labelings, which is motivated by the channel assignmentproblem. We consider the question of finding the minimum edge span beta_d( G) of this labeling.Several classes of graphs such as cycles, trees, complete k-partite graphs, chordal graphs includingtriangular lattice and square lattice which are important to a telecommunication problem arestudied, and exact values are given.
