Optimal L(j, k)-Edge-Labeling of Regular Grids

 

T. Calamoneri

Abstract

Given a graph G = (V, E) and two positive integers j and k, an L(j, k)-edge-labeling is a function f assigning to edges of E colors from a set {0, 1, . . . , kf } such that |f(e)?f(e?)| ? j if e and e? are adjacent, i.e. they share a common endpoint, |f(e) ? f(e?)| ? k if e and e? are not adjacent and there exists an edge adjacent to both e and e?. The aim of the L(j, k)-edge-labeling problem consists of finding a coloring function f such that the value of kf is minimum. This minimum value is called ??j,k(G). This problem has already been studied on hexagonal, squared and triangular grids, but mostly not coinciding upper and lower bounds on ??j,k have been proposed. In this paper we close some of these gaps or find better bounds on ??j,k in the special cases j = 1,2 and k = 1. Moreover, we propose tight L(j,k)-edge-labelings for eight-regular grids.

PDF Files

Journal Version