$L(j,k)$-Labelings of the Cartesian Products of Complete Graphs

Damei Lv, Wensong Lin and Zengmin Song
1 Department of Mathematics, Nantong University, Nantong 210007, P. R. China
2 Department of Mathematics, Southeast University, Nanjing 210096, P. R. China

Abstract     Full Text  PPT

For positive integers $j$ and $k$, $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 $\lambda_{k}^{j}$-number of $G$ is the minimum span taken over all $L(j,\,k)$-labelings of $G$. In this paper, we extend the previous work on the $\lambda_{k}^{j}$-number of the Cartesian products of complete graphs. For $n> m\geq l$ and $n> 2m>4$, we show $\lambda_{k}^{j}(K_{n}\times K_{m}\times K_{l})=(nm-1)k $ if $j/k\leq m$, and that $\lambda_{k}^{j}(K_{n}\times K_{m}\times K_{l})=(n-1)j+(m-1)k$ if $j/k\geq m$. For $n> m\geq l$ and $n= 2m>4$, we show $\lambda_{k}^{j}(K_{n}\times K_{m}\times K_{l})=(nm-1)k $ if $j/k\leq m-1$, and that $\lambda_{k}^{j}(K_{n}\times K_{m}\times K_{l})\leq(n-1)(j+k)+(m-1)k$ if $j/k\geq m-1$. We also study $\lambda_{k}^{j}(K_{n}\times K_{m}\times K_{l})$ when $m\leq n <2m$.