# On distance two labelling of unit interval graphs

Peter Che Bor Lam, Tao Ming Wang, Wai Chee SHIU, Guohua Gu

Research output: Contribution to journalJournal articlepeer-review

## 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 1167-1179 13 Taiwanese Journal of Mathematics 13 4 https://doi.org/10.11650/twjm/1500405499 Published - Aug 2009

## Scopus Subject Areas

• Mathematics(all)

## User-Defined Keywords

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

## Fingerprint

Dive into the research topics of 'On distance two labelling of unit interval graphs'. Together they form a unique fingerprint.
{"ft_lang_label":"__label__en","ft_lang_prob":0.83559895,"math_prob":0.66121405,"size":1002,"snap":"2023-40-2023-50","text_gpt3_token_len":280,"char_repetition_ratio":0.121242486,"word_repetition_ratio":0.0,"special_character_ratio":0.26546907,"punctuation_ratio":0.06282722,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97873443,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-10-03T17:26:00Z\",\"WARC-Record-ID\":\"<urn:uuid:1cf34c5d-0af4-4db7-984d-c2b3e7e64492>\",\"Content-Length\":\"49820\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9d79f419-6559-468f-889a-bb390cb3a3c9>\",\"WARC-Concurrent-To\":\"<urn:uuid:09bf6edc-4bd4-4305-a23c-7748c19ac96e>\",\"WARC-IP-Address\":\"52.74.61.34\",\"WARC-Target-URI\":\"https://scholars.hkbu.edu.hk/en/publications/on-distance-two-labelling-of-unit-interval-graphs-10\",\"WARC-Payload-Digest\":\"sha1:SDC3YCFTSL5JIKXSOUX4W3HH7M7CDOH2\",\"WARC-Block-Digest\":\"sha1:QZR6RTADMY3DSNIUPEOPYPXNEYDT7ULC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233511170.92_warc_CC-MAIN-20231003160453-20231003190453-00119.warc.gz\"}"}