Tiziana Calamoneri - Optimal L(h,k)-Labeling of Regular Grids

dmtcs:361 - Discrete Mathematics & Theoretical Computer Science, January 1, 2006, Vol. 8 - https://doi.org/10.46298/dmtcs.361
Optimal L(h,k)-Labeling of Regular Grids

Authors: Tiziana Calamoneri ORCID-iD1

  • 1 Dipartimento di Informatica

The L(h, 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 L(h,k)-labeling is the difference between the largest and the smallest assigned label. We study L(h, k)-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The L(h,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 L(h,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.


Volume: Vol. 8
Published on: January 1, 2006
Imported on: March 26, 2015
Keywords: squared grids,hexagonal grids,L(h,k)-labeling,cellular grids,triangular grids,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1401.6583
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1401.6583
  • 1401.6583
  • 10.48550/arxiv.1401.6583
The Radio Number of Grid Graphs

13 Documents citing this article

Consultation statistics

This page has been seen 238 times.
This article's PDF has been downloaded 198 times.