DIMACS TR: 2003-33

L(2,1)-Labelings of Products of Two Cycles

Authors: Christopher Schwarz and Denise Sakai Troxell


An L(2,1)-labeling of a graph is an assignment of nonnegative integers to its vertices so that adjacent vertices get labels at least two apart and vertices at distance two get distinct labels. The $\lambda$-number of a graph G, denoted by $\lambda(G)$, is the minimum range of labels taken over all of its L(2,1)-labelings. We show that the $\lambda$-number of the Cartesian product of any two cycles is 6, 7 or 8. In addition, we provide complete characterizations for the products of two cycles with $\lambda$-number exactly equal to each one of these values.

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-33.ps.gz
DIMACS Home Page