Distance Labelings of Graphs

Abstract

An $L(2,1)$-labelling of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all nonnegative integers such that $|f(x)–f(y)|\ge 2$ if $d(x,y)=1$ and $|f(x)–f(y)|\ge 1$ if $d(x,y)=2$, where $d(x,y)$ denotes the distance between $x$ and $y$ in $G$. The $(2,1)$-labelling number $\lambda (G)$ of $G$ is the smallest number $k$ such that $G$ has an $L(2,1)$-labelling with $max\{f(v):v\in V(G)\}=k$. Griggs and Yeh conjecture that $\lambda (G)\le {\mathrm{\Delta }}^2$ for any simple graph with maximum degree $\mathrm{\Delta }\ge 2$. This article considers the graphs formed by the cartesian product of $n$ ($n\ge 2$ graphs. The new graph satisfies the above conjecture (with minor exceptions). Moreover, we generalize our results in [19].