#### Document Type

Article

#### Department

â€‹Mathematics

#### Publication Date

2005

#### Abstract

For a graph *G*, an *L*(2,1)-labeling of *G* with span *k* is a mapping $L \right arrow \{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$.

## Comments

Originally published in

SIAM J. Discrete Math. 19, pp. 208-223. http://dx.doi.org/10.1137/S0895480103429800Provided by the Trinity College Digital Repository in accordance with the publisher's archiving policies.