episciences.org_361_20230328204356216
20230328204356216
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2006
Vol. 8
Optimal L(h,k)Labeling of Regular Grids
Tiziana
Calamoneri
https://orcid.org/0000000240991836
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.
01
01
2006
361
https://hal.science/hal00961106v1
10.46298/dmtcs.361
https://dmtcs.episciences.org/361

https://dmtcs.episciences.org/361/pdf

https://dmtcs.episciences.org/361/pdf