L(2,1)-Circular Labelings of Cartesian Products of Complete Graphs

Abstract:

      For positive integers $j$ and $k$ with $j\geq k$, an $L(j,k)$-labeling of a graph $G$ is an assignment of nonnegative integers to $V(G)$ such that the difference between labels of adjacent vertices is at least $j$, and the difference between labels of vertices that are distance two apart is at least $k$. The span of an $L(j,k)$-labeling of a graph $G$ is the difference between the maximum and minimum integers it uses. The $\lambda_{j,k}$-number of $G$ is the minimum span taken over all $L(j,k)$-labelings of $G$. An $m$-$(j,k)$-circular labeling of a graph $G$ is a function $f: V(G)\rightarrow \{0,1,2,\ldots,m-1\}$ such that $|f(u)-f(v)|_{m}\geq j$ if $u$ and $v$ are adjacent; and $|f(u)-f(v)|_{m}\geq k$ if $u$ and $v$ are at distance two, where $|x|_{m}=\min\{|x|,m-|x|\}$. The minimum integer $m$ such that there exists an $m$-$(j,k)$-circular labeling of $G$ is called the $\sigma_{j,k}$-number of $G$ and is denoted by $\sigma_{j,k}(G)$. This paper determines the $\sigma_{2,1}$-number of the Cartesian product of any three complete graphs.