L(2,1)-Circular Labelings of Cartesian Products of Complete Graphs
Received:December 17, 2006  Revised:September 04, 2007
Key Word: $\lambda_{2,1}$-number   $\sigma_{2,1}$-number   Cartesian product.
Fund ProjectL:the National Natural Science Foundation of China (No.10671033); the Science Foundation of Southeast University (No.XJ0607230); the Natural Science Foundation of Nantong University (No.08Z003).
 Author Name Affiliation LU Da Mei Department of Mathematics, Nantong University, Jiangsu 226001, China LIN Wen Song Department of Mathematics, Southeast University, Jiangsu 210096, China SONG Zeng Min Department of Mathematics, Southeast University, Jiangsu 210096, China
Hits: 11832
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.