DIMACS TR: 93-11
The L(2,1)-Labeling Problem on Graphs
Authors: Gerard J. Chang and David Kuo
ABSTRACT
An L(2,1)-labeling of a graph G is a function f from the vertex set V(G)
to the set of all nonnegative integers such that f(x) and f(y) differ by
at least two if x is adjacent to y, and f(x) differs from f(y) if x is of
distance two from y. The L(2,1)-labeling number of a graph G is the smallest
number k such that G has an L(2,1)-labeling with max {f(v): v in V(G)} = k.
In this paper, we give exact formulas of the L(2,1)-labelings of the union
and the join of two graphs. We also prove that the L(2,1)-labeling number
of a graph G of maximum degree D is at most D(D+1). For OSF-chordal graphs,
the upper bound can be reduced to 2D+1. For SF-chordal graphs, the upper
bound can be reduced to D+2C-2, where C is the chromatic number of G. Finally,
we present a polynomial time algorithm to determine the L(2,1)-labeling number
of a tree.
Keywords: L(2,1)-labeling, T-coloring, union, join, chordal graph, perfect
graph, tree, bipartite matching, algorithm
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-11.ps
DIMACS Home Page