## Abstract

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).

Original language | English |
---|---|

Pages (from-to) | 1167-1179 |

Number of pages | 13 |

Journal | Taiwanese Journal of Mathematics |

Volume | 13 |

Issue number | 4 |

DOIs | |

Publication status | Published - Aug 2009 |

## Scopus Subject Areas

- Mathematics(all)

## User-Defined Keywords

- L(2,1)-labelling
- Unit interval graph