Edge span of L(d, 1)-labeling on some graphs

摘要

Given a graph G and a positive integer d, an L( d, 1) -labeling of G is a function / that assigns to each vertex of G a non-negative integer such that |f(u)-f (v) | >=d if d_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 the minimum range span of labels over all such labelings, which is motivated by the channel assignment problem. 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 including triangular lattice and square lattice which are important to a telecommunication problem are studied, and exact values are given.