Korean J. Math.  Vol 21, No 2 (2013)  pp.151-159
DOI: https://doi.org/10.11568/kjm.2013.21.2.151

The $\lambda$-number of the Cartesian product of a complete graph and a cycle

Byeong Moon Kim, Byung Chul Song, Yoomi Rho


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\square 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\ge3$, $\lambda(K_4\square C_{n})$ $\ge7$ and the equality holds if and only if $n$ is a multiple of $8$. Moreover when $m\ge5$, $\lambda(K_m\square C_{n})\ge 2m-1$ and the equality holds if and only if $n$ is even.

Subject classification



Full Text:



  • There are currently no refbacks.

ISSN: 1976-8605 (Print), 2288-1433 (Online)

Copyright(c) 2013 By The Kangwon-Kyungki Mathematical Society, Department of Mathematics, Kangwon National University Chuncheon 21341, Korea Fax: +82-33-259-5662 E-mail: kkms@kangwon.ac.kr