Optimal $L(\delta_1,\delta_2,1)$-Labeling of Eight-Regular Grids

T. Calamoneri

Abstract

Given a graph $G=(V,E)$, an $L(\delta_1,\delta_2,\delta_3)$-labeling is a function $f$ assigning to nodes of $V$ colors from a set $\{ 0, 1, \ldots , k_f \}$ such that $|f(u)-f(v)| \geq \delta_i$ if $u$ and $v$ are at distance $i$ in $G$. The aim of the $L(\delta_1,\delta_2,\delta_3)$-labeling problem consists of finding a coloring function $f$ such that the value of $k_f$ is minimum. This minimum value is called $\lambda_{\delta_1, \delta_2, \delta_3}(G)$. In this paper we study this problem on the eight-regular grids for the special values $(\delta_1, \delta_2, \delta_3)=(3,2,1)$ and $(\delta_1, \delta_2, \delta_3)=(2,1,1)$, providing optimal labelings. Furthermore, exploiting the lower bound technique, we improve the known lower bound on $\lambda_{3,2,1}$ for triangular grids.

PDF Files

Journal Version