For a graph G, an L(2,1)-labeling of G with span k is a mapping $L \rightarrow \{0, 1, 2, \ldots, k\}$ such that adjacent vertices are assigned integers which differ by at least 2, vertices at distance two are assigned integers which differ by at least 1, and the image of L includes 0 and k. The minimum span over all L(2,1)-labelings of G is denoted $\lambda(G)$, and each L(2,1)-labeling with span $\lambda(G)$ is called a $\lambda$-labeling. For $h \in \{1, \ldots, k-1\}$, h is a hole of L if and only if h is not in the image of L. The minimum number of holes over all $\lambda$-labelings is denoted $\rho(G)$, and the minimum k for which there exists a surjective L(2,1)-labeling onto {0,1, ..., k} is denoted $\mu(G)$. This paper extends the work of Fishburn and Roberts on $\rho$ and $\mu$ through the investigation of an equivalence relation on the set of $\lambda$-labelings with $\rho$ holes. In particular, we establish that $\rho \leq \Delta$. We analyze the structure of those graphs for which $\rho \in \{ \Delta-1, \Delta \}$, and we show that $\mu = \lambda+ 1$ whenever $\lambda$ is less than the order of the graph. Finally, we give constructions of connected graphs with $\rho = \Delta$ and order $t(\Delta + 1)$, $1 \leq t \leq \Delta$.

For positive integers $j \geq k$, the $\lambda_{j,k}$-number of graph G is the smallest span among all integer labelings of V(G) such that vertices at distance two receive labels which differ by at least k and adjacent vertices receive labels which differ by at least j. We prove that the $\lambda_{j,k}$-number of any r-regular graph is no less than the $\lambda_{j,k}$-number of the infinite r-regular tree $T_{\infty}(r)$. Defining an r-regular graph G to be $(j,k,r)$-optimal if and only if $\lambda_{j,k}(G) = \lambda_{j,k}(T_{\infty}(r))$, we establish the equivalence between $(j,k,r)$-optimal graphs and r-regular bipartite graphs with a certain edge coloring property for the case ${j \over k} > r$. The structure of r-regular optimal graphs for ${j \over k} \leq r$ is investigated, with special attention to ${j \over k} = 1,2$. For the latter, we establish that a (2,1,r)-optimal graph, through a series of edge transformations, has a canonical form. Finally, we apply our results on optimality to the derivation of the $\lambda_{j,k}$-numbers of prisms.

For integers $j \geq k$, an L(j,k)-labeling of a graph G is an integer labeling of the vertices in V(G) such that adjacent vertices receive integers which differ by at least j, and vertices which are distance two apart receive labels which differ by at least k. We determine $\lambda^j_k(K_n \times K_m)$ for all j,k,m,n, and $\lambda^{2}_1(K^q_{p^r})$ for $3 \leq q < p$, p prime.

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.