DIMACS TR: 2003-33
L(2,1)-Labelings of Products of Two Cycles
Authors: Christopher Schwarz and Denise Sakai Troxell
ABSTRACT
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