## DIMACS TR: 2004-43

##
On Critical Trees Labeled with a Condition at Distance Two

### Author: 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. A graph is
said to be lambda-critical if lambda is the minimum span taken over all
of its L(2,1)-labelings, and every proper subgraph has an L(2,1)-labeling
with span strictly smaller than lambda. Georges and Mauro have studied
5-critical trees with maximum degree 3 by examining their path-like
substructures. They also presented an infinite family of 5-critical trees
of maximum degree 3. We generalize these results for lambda-critical
trees with maximum degree greater than 3.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-43.ps.gz

DIMACS Home Page