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 L(2,1)-labelling problem and the importance of surjective L(2,1)-labelling problem, we consider surjective L(2,1)-labelling (SL21-labelling) problems for paths and interval graphs. For any graph G = (V, E), an SL21-labelling is a mapping phi: V -> {1, 2, ... , n} so that, for every pair of nodes u and v, if d(u, v =1), then phi(u-phi(v) >= 2; and if d(u, v) = 2, then vertical bar phi(u) - phi(v)vertical bar >= 1, and every label 1,2, ... , n is used exactly once, where d(u,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 L(2,1)-labelled if n >= 4, and it is also proved that any interval graph (IG) G having n nodes and degree Delta > 2 can be surjectively L(2,1)-labelled if n = 3 Delta - 1. Also, we have designed two efficient algorithms for surjective L(2,1)-labelling of paths and interval graphs. The results regarding both paths and interval graphs are the first result for surjective L(2,1)-labelling.