On the L(2, 1)-labelling of block graphs

Abstract

The distance-two labelling 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)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k.

In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3.

Keywords:

• block graphs
• distance-two labelling problem
• graph colouring

2010 AMS Subject Classification :

• 05C15

ACM Computing Classification System Code :

• G.2.2

Acknowledgements

This work was partially supported by the CAPES/SPU Project CAPG-BA 008/02 and Math-AmSud Project 10MATH-04. F.B. was partially supported by ANPCyT PICT-2007-00518 and PICT-2007-00533, and UBACyT Grants X069 and X606 (Argentina). M.R.C was partially supported by CNPq and FAPERJ (Brazil).