Distance Two Labelings of Cartesian Products of Complete Graphs

Abstract

For two positive integers $j$ and $k$ with $j\ge 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 used by it. The ${\lambda }_{j,k}$-number of $G$ is the minimum span over all $L(j,k)$-labelings of $G$. This paper focuses on the ${\lambda }_{2,1}$-number of the Cartesian products of complete graphs. We completely determine the ${\lambda }_{2,1}$-numbers of the Cartesian products of three complete graphs $K_n$, $K_m$, and $K_l$: for any three positive integers $n$, $m$, and $l$.