Author(s): YUAN WAN-LIAN, ZHAI MING-QING, LU CHANG-HONG
Pages: 79-87
Year: 2009 Issue:  1
Journal: Northeastern Mathematical Journal
Keyword:  channel assignment problems;  L(2; 1)-labeling;  L(3;  2; 1)-labeling;  bi-partite graph;  tree;
Abstract: An L(3, 2,1)-labeling of a graph G is a function from the vertex set V(G) to the set of all nonnegative integers such that |f(υ) - f(ν)|≥ 3 if dG(υ,ν) = 1, |f(υ) - f(ν)|≥ 2 if dG(υ,ν) = 2, and |f(υ) - f(ν)|≥ 1 if dG(υ,ν) = 3. The L(3, 2,1)-labeling problem is to find the smallest number λ3(G) such that there ex-ists an L(3, 2,1)-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds ofλ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3(T) attains the minimum value.