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.
2006
l (h; k)-labeling; l(h; maximum degree; tree; vertex labeling
01 Pubblicazione su rivista::01a Articolo in rivista
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].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/233693
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 24
social impact