On the L(2,1)-labeling of block graphs
BONOMO, FLAVIA; CERIOLI, MARCIA R.
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Francis & Taylor and IT Consultant
Año: 2011 vol. 88 p. 468 - 475
The distance-two labeling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and nonconsecutive integers. The L(2,1)-labeling number of G, denoted by lambda(G), is the smallest integer k such that G has an L(2,1)-labeling in which no label is greater than k.In this work we study the L(2,1)-labeling problem on block graphs. We find upper bounds for lambda(G) in the general case, and we reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3.