#### Title

On the Hole Index of L(2,1)-Labelings of r-Regular Graphs

#### 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 *l(G),* is the minimum span taken over all L(2,1)-labelings of *G*. The hole index of a graph *G, *denoted *r(G), *is the minimum number of holes taken over all L(2,1)-labelings with span exactly *l(G)*. Georges and Mauro [SIAM J. Discrete Math., 19 (2005) 208—223] conjectured that if *G* is an *r*-regular graph and *r(G) ≥ 1,* then *r(G)* must divide *r*. We show that this conjecture does not hold by providing an infinite number of *r*-regular graphs *G* such that *r(G)* and *r* are relatively prime integers.

#### Academic Division

Math/Science

#### Disciplines

Discrete Mathematics and Combinatorics

#### Recommended Citation

Troxell, Denise Sakai; Adams, Sarah Spence; Tesch, Matthew; Westgate, Bradford; and Wheeland, Cody, "On the Hole Index of L(2,1)-Labelings of r-Regular Graphs" (2008). *Babson Faculty Research Fund Working Papers*. 20.

https://digitalknowledge.babson.edu/bfrfwp/20

## Comments

For full text, please seeDiscrete Applied MathematicsVolume 155, Issue 17, 15 October 2007, Pages 2391-2393; doi: http://dx.doi.org/10.1016/j.dam.2007.07.009