Distance two surjective labelling of paths and interval graphs (Q2045355)

Summary: 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 (\(\mathrm{SL}21\))-labelling) problems for paths and interval graphs. For any graph \(G=(V,E)\), an \(\mathrm{SL}21\)-labelling is a mapping \(\varphi:V\longrightarrow\{1,2, \dots,n\}\) so that, for every pair of nodes \(u\) and \(v\), if \(d(u,v)=1\), then \(|\varphi (u)-\varphi (v)|\geq2\); and if \(d(u,v)=2\), then \(|\varphi(u)-\varphi (v)|\geq1\), and every label \(1,2,\dots,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 \(P_n\) can be surjectively \(L(2,1)\)-labelled if \(n\geq4\), 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.