Given two nonnegative integers h and k, an L(h, k)-labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)-labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)-labeling problem is NP-complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co-comparability graphs, its subclass of interval graphs, and circular-arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)-labeling of co-comparability and circular-arc graphs. In particular, we provide the first algorithm to L(h, k)-label co-comparability, interval, and circular-arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously-known ones using a number of colors that is at most twice the optimum.

On the L(h,k)-Labeling Co-Comparability Graphs and Circular-Arc Graphs / Calamoneri, Tiziana; Caminiti, S; Olariu, S; Petreschi, Rossella. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 53:1(2009), pp. 27-34. [10.1002/net.20257]

On the L(h,k)-Labeling Co-Comparability Graphs and Circular-Arc Graphs

CALAMONERI, Tiziana;PETRESCHI, Rossella
2009

Abstract

Given two nonnegative integers h and k, an L(h, k)-labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)-labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)-labeling problem is NP-complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co-comparability graphs, its subclass of interval graphs, and circular-arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)-labeling of co-comparability and circular-arc graphs. In particular, we provide the first algorithm to L(h, k)-label co-comparability, interval, and circular-arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously-known ones using a number of colors that is at most twice the optimum.
2009
L(h; k)-Labeling; co-comparability graphs; interval graphs; circular-arc graphs
01 Pubblicazione su rivista::01a Articolo in rivista
On the L(h,k)-Labeling Co-Comparability Graphs and Circular-Arc Graphs / Calamoneri, Tiziana; Caminiti, S; Olariu, S; Petreschi, Rossella. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 53:1(2009), pp. 27-34. [10.1002/net.20257]
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/33466
 Attenzione

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

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