Distance Two Surjective Labelling of Paths and Interval Graphs

Abstract

Graph labelling problem has been broadly studied for a long period for its applications, especially in frequency assignment in (mobile) communication system, X-ray crystallography, circuit design, etc. Nowadays, surjective L2,1-labelling is a well-studied problem. Motivated from the L2,1-labelling problem and the importance of surjective L2,1-labelling problem, we consider surjective L2,1-labelling (SL21-labelling) problems for paths and interval graphs. For any graph G=V,E, an SL21-labelling is a mapping φ:V⟶1,2,…,n so that, for every pair of nodes u and v, if du,v=1, then φu−φv≥2; and if du,v=2, then φu−φv≥1, and every label 1,2,…,n is used exactly once, where du,v represents the distance between the nodes u and v, and n is the number of nodes of graph G. In the present article, it is proved that any path Pn can be surjectively L2,1-labelled if n≥4, and it is also proved that any interval graph IGG having n nodes and degree Δ>2 can be surjectively L2,1-labelled if n=3Δ−1. Also, we have designed two efficient algorithms for surjective L2,1-labelling of paths and interval graphs. The results regarding both paths and interval graphs are the first result for surjective L2,1-labelling.