On $(s,t)$-Relaxed $L(2,1)$-Labelings of the Hexagonal Lattice

Abstract

Suppose $G$ is a graph. Let $u$ be a vertex of $G$. A vertex $v$ is called an $i$-neighbor of $u$ if $d_G(u,v)=i$. A $1$-neighbor of $u$ is simply called a neighbor of $u$. Let $s$ and $t$ be two nonnegative integers. Suppose $f$ is an assignment of nonnegative integers to the vertices of $G$. If the following three conditions are satisfied, then $f$ is called an $(s,t)$-relaxed $L(2,1)$-labeling of $G$: (1) for any two adjacent vertices $u$ and $v$ of $G$, $f(u)\ne f(v)$; (2) for any vertex $u$ of $G$, there are at most $s$ neighbors of $u$ receiving labels from $\{f(u)–1,f(u)+1\}$; (3) for any vertex $u$ of $G$, the number of $2$-neighbors of $u$ assigned the label $f(u)$ is at most $t$. The minimum span of $(s,t)$-relaxed $L(2,1)$-labelings of $G$ is called the $(s,t)$-relaxed $L(2,1)$-labeling number of $G$, denoted by ${\lambda }_{2,1}^{s,t}(G)$. It is clear that ${\lambda }_{2,1}^{0,0}(G)$ is the so-called $L(2,1)$-labeling number of $G$. In this paper, the $(s,t)$-relaxed $L(2,1)$-labeling number of the hexagonal lattice is determined for each pair of two nonnegative integers $s$ and $t$. And this provides a series of channel assignment schemes for the corresponding channel assignment problem on the hexagonal lattice.