On the Hole Index of L(2,1)-Labelings of r-Regular Graphs
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.
Discrete Mathematics and Combinatorics
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.