#### Title

On the hole index of L(2,1)-labelings of r-regular graphs

#### Publication

Discrete Applied Mathematics

#### DOI*

http://dx.doi.org/10.1016/j.dam.2007.07.009

#### Abstract

An L(2,1)-labeling of a graph *G* is an assignment of nonnegative integers to the vertices of *G* so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph *G*, denoted *λ*(*G*), is the minimum span taken over all L(2,1)-labelings of *G*. The hole index of a graph *G*, denoted *ρ*(*G*), is the minimum number of holes taken over all L(2,1)-labelings with span exactly *λ*(*G*). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223] conjectured that if *G* is an *r*-regular graph and *ρ*(*G*) 1, then *ρ*(*G*) must divide *r*. We show that this conjecture does not hold by providing an infinite number of *r*-regular graphs *G* such that *ρ*(*G*) and *r* are relatively prime integers.

#### Disciplines

Applied Mathematics

#### Recommended Citation

Adams, S. S., M. Tesch, D.S. Troxell, B. Westgate, C. Wheeland. 2007. "On the hole index of L(2,1)-labelings of r-regular graphs." S.S. Adams, M. Tesch, D.S. Troxell, B. Westgate, C. Wheeland, *Discrete Applied Mathematics* 155, 2391-2393.

(With S. S. Adams, M. Tesch, B. Westgate, and C. Wheeland)