Topologie di interconnessione in reti mobili

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.(Labeling trees with a condition at distance two, Proc. R. C. Bose Centenary Symp. On Discrete Math. And Applications, Electronic Notes in Discrete Mathematics vol. 15/2003, pp. 1-4, 2002. and T. Calamoneri, A. Pelc, R. Petreschi, Labeling trees with a condition at distance two, Discrete Mathematics, 306(14), pp. 1534-1539, 2006).