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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.