THE λ-NUMBER OF THE CARTESIAN PRODUCT OF A COMPLETE GRAPH AND A CYCLE
Byeong Moon Kim, Byung Chul Song, Yoomi Rho · Korean Journal of Mathematics · 2013
An $L(j,k)$ -labeling of a graph G is a vertex labeling such that the difference of the labels of any adjacent vertices is at least $j$ and that of any vertices of distance two is at least $k$ for given $j$ and $k$ . The minimum span of all L(2, 1)-labelings of G is called the ${\lambda}$ -number of G and is denoted by ${\lambda}(G)$ . In this paper, we find a lower bound of the ${\lambda}$ -number of the Cartesian product $K_m{\Box}C_n$ of the complete graph $K_m$ of order $m$ and the cycle $C_n$ of order $n$ . In fact, we show that when $n{\geq}3$ , ${\lambda}(K_4{\Box}C_n){\geq}7$ and the equality holds if and only if n is a multiple of 8. Moreover when $m{\geq}5$ , ${\lambda}(K_m{\Box}C_n){\geq}2m-1$ and the equality holds if and only if $n$ is even.