An L(h, k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h, k)-labeling is the difference between the largest and the smallest label. We investigate L(h, k)-labelings of trees of maximum degree Delta, seeking those with small span. Given Delta, h and k, span lambda is optimal for the class of trees of maximum degree Delta, if lambda is the smallest integer such that every tree of maximum degree Delta has an L(h, k)-labeling with span at most lambda. For all parameters Delta, h, k, such that h < k, we construct L(h, k)-labelings with optimal span. We also establish optimal span of L(h, k)-labelings for stars of arbitrary degree and all values of h and k. (c) 2006 Elsevier B.V. All rights reserved.
Labeling trees with a condition at distance two / Calamoneri, Tiziana; Andrzej, Pelc; Petreschi, Rossella. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 306:14(2006), pp. 1534-1539. (Intervento presentato al convegno Symposium on Discrete Mathematics and Applications held in honor of RC Bose tenutosi a Kolkata, INDIA nel DEC, 2002) [10.1016/j.disc.2005.04.024].
Labeling trees with a condition at distance two
CALAMONERI, Tiziana;PETRESCHI, Rossella
2006
Abstract
An L(h, k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h, k)-labeling is the difference between the largest and the smallest label. We investigate L(h, k)-labelings of trees of maximum degree Delta, seeking those with small span. Given Delta, h and k, span lambda is optimal for the class of trees of maximum degree Delta, if lambda is the smallest integer such that every tree of maximum degree Delta has an L(h, k)-labeling with span at most lambda. For all parameters Delta, h, k, such that h < k, we construct L(h, k)-labelings with optimal span. We also establish optimal span of L(h, k)-labelings for stars of arbitrary degree and all values of h and k. (c) 2006 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.