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 at most two get different numbers and adjacent vertices get numbers which are at least two apart. The L(2, 1)-labelling number of G, denoted by λ(G), is the minimum range of labels over all such labellings. In this paper, we first discuss some necessary and sufficient conditions for unit interval graph G to have λ(G) = 2χ(G) - 2 and then characterize all unit interval graphs G of order no more than 3χ(G) - 1, where χ(G) is the chromatic number of G. Finally, we discuss some subgraphs of unit interval graphs G on more than 2χ(G) + 1 vertices with λ(G) = 2χ(G).
Scopus Subject Areas
- Unit interval graph