On the Structure of Graphs with Non-Surjective <i>L</i>(2,1)-Labelings

Abstract

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$.