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.展开更多
L(d, 1)-labeling is a kind of graph coloring problem from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least d apart while nodes at distance two from each other must ...L(d, 1)-labeling is a kind of graph coloring problem from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least d apart while nodes at distance two from each other must receive different colors. We focus on L(d, 1)-labeling of regular tilings for d≥3 since the cases d=0, 1 or 2 have been researched by Calamoneri and Petreschi. For all three kinds of regular tilings, we give their L (d, 1)-labeling numbers for any integer d≥3. Therefore, combined with the results given by Calamoneri and Petreschi, the L(d, 1)-labeling numbers of regular tilings for any nonnegative integer d may be determined completely.展开更多
文摘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.
文摘L(d, 1)-labeling is a kind of graph coloring problem from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least d apart while nodes at distance two from each other must receive different colors. We focus on L(d, 1)-labeling of regular tilings for d≥3 since the cases d=0, 1 or 2 have been researched by Calamoneri and Petreschi. For all three kinds of regular tilings, we give their L (d, 1)-labeling numbers for any integer d≥3. Therefore, combined with the results given by Calamoneri and Petreschi, the L(d, 1)-labeling numbers of regular tilings for any nonnegative integer d may be determined completely.
