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

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.141-158
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00961106
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 19 mars 2014 - 14:31:05
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : jeudi 19 juin 2014 - 11:58:31

Fichier

dm080109.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00961106, version 1

Collections

Citation

Tiziana Calamoneri. Optimal L(h,k)-Labeling of Regular Grids. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.141-158. 〈hal-00961106〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

293