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


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


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



Discrete Mathematics and Combinatorics

This document is currently not available here.