{"docId":361,"paperId":361,"url":"https:\/\/dmtcs.episciences.org\/361","doi":"10.46298\/dmtcs.361","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":80,"name":"Vol. 8"}],"section":[],"repositoryName":"Hal","repositoryIdentifier":"hal-00961106","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00961106v1","dateSubmitted":"2015-03-26 16:18:54","dateAccepted":"2015-06-09 14:46:10","datePublished":"2006-01-01 08:00:00","titles":{"en":"Optimal L(h,k)-Labeling of Regular Grids"},"authors":["Calamoneri, Tiziana"],"abstracts":{"en":"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 \u2265 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 \u03bb -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."},"keywords":[["squared grids"],["hexagonal grids"],["L(h"],["k)-labeling"],["cellular grids"],["triangular grids"],"[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}