$L(2,1)$-Labeling of a Circular Graph

Abstract

In this paper, the $\lambda$-number of the circular graph $C(km,m)$ is shown to be at most $9$ where $m\ge 3$ and $k\ge 2$, and the $\lambda$-number of the circular graph $C(km+s,m)$ is shown to be at most $15$ where $m\ge 3$, $k\ge 2$, and $1\le s\le m-1$. In particular, the $\lambda$-numbers of $C(2m,m)$ and $C(n,2)$ are determined, which are at most $8$. All our results indicate that Griggs and Yeh’s conjecture holds for circular graphs. The conjecture says that for any graph $G$ with maximum degree $\mathrm{\Delta }\ge 2$, $\lambda (G)\le {\mathrm{\Delta }}^2$. Also, we determine $\lambda$-numbers of $C(n,3)$, $C(n,4)$, and $C(n,5)$ if $n\equiv 0(\mathrm{mod}7)$.