2004-43: On Critical Trees Labeled with a Condition at Distance Two

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