Optimal Lh,k-Labeling of Regular GridsReport as inadecuate

Optimal Lh,k-Labeling of Regular Grids - Download this document for free, or read online. Document in PDF available to download.

1 Dipartimento di Informatica

Abstract : The Lh, k-labeling is an assignment of non negative integer labels to the nodes of a graph such that -close- nodes have labels which differ by at least k, and -very close- nodes have labels which differ by at least h. The span of an Lh,k-labeling is the difference between the largest and the smallest assigned label. We study Lh, k-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The Lh,k-labeling problem has been intensively studied in some special cases, i.e. when k=0 vertex coloring, h=k vertex coloring the square of the graph and h=2k radio- or λ -coloring but no results are known in the general case for regular grids. In this paper, we completely solve the Lh,k-labeling problem on regular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds.

Keywords : squared grids hexagonal grids Lh k-labeling cellular grids triangular grids

Author: Tiziana Calamoneri -

Source: https://hal.archives-ouvertes.fr/


Related documents