On the hole index of L(2,1)-labelings of r-regular graphs
Discrete Applied Mathematics
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.
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.