Distance two surjective labelling of paths and interval graphs

摘要: 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 is a well‐studied problem. Motivated from the 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 φ : V⟶{1,2, …, n} so that, for every pair of nodes u and v, if d(u, v) = 1, then |φ(u) − φ(v)| ≥ 2; and if d(u, v) = 2, then |φ(u) − φ(v)| ≥ 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 …