HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00961106
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, March 19, 2014 - 2:31:05 PM
Last modification on : Wednesday, November 3, 2021 - 2:18:08 PM
Long-term archiving on: : Thursday, June 19, 2014 - 11:58:31 AM

File

dm080109.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Tiziana Calamoneri. Optimal L(h,k)-Labeling of Regular Grids. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, Vol. 8, pp.141-158. ⟨10.46298/dmtcs.361⟩. ⟨hal-00961106⟩

Share

Metrics

Record views

66

Files downloads

800