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

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, ldots , k_f }$ such that $|f(e)-f(e')| geq j$ if $e$ and $e'$ are adjacent, i.e. they share a common endpoint, $|f(e)-f(e')| geq 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 $k_f$ is minimum. This minimum value is called $lambda'_{j,k}(G)$. This problem has already been studied on hexagonal, squared and triangular grids, but mostly not coinciding upper and lower bounds on $lambda'_{j,k}$ have been proposed. In this paper we close some of these gaps or find better bounds on $lambda'_{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.