On the $\lambda$-Number of $Q_n $ and Related Graphs

Abstract

An $L( 2,1)$-labeling of graph G is an integer labeling of $V( G )$ such that adjacent vertices have labels that differ by at least 2 and such that vertices distance 2 apart have labels that differ by at least 1. The $\lambda $-number of G, $\lambda ( G )$, is the minimum range over all $L( 2,1)$-labelings. We examine the properties of $\lambda $-labelings of the n-cube $Q_n $. Griggs and Yeh have determined $\lambda ( Q_n )$ for $n \leq 5$ and have established $n + 3 \leq \lambda ( Q_n ) \leq 2n + 1\,{\text{for}}\,n \geq 6$. We modify a technique used in coding theory to improve the upper bound. We also examine the $\lambda$-labelings of related graphs, such as the subdivision of the n-cube and the Cartesian products of paths.