Summary: Given a simple graph \(G=(V,E)\) and a positive number \(d\), an \(L_ d(2,1)\)-labelling of \(G\) is a function \(f: V(G)\to [0,\infty)\) such that whenever \(x,y\in V\) are adjacent, \(| f(x)-f(y)|\geq 2d\), and whenever the distance between \(x\) and \(y\) is two, \(| f(x)- f(y)|\geq d\). The \(L_ d(2,1)\)-labelling number \(\lambda(G,d)\) is the smallest number \(m\) such that \(G\) has an \(L_ d(2,1)\)-labelling \(f\) with \(\max\{f(v): v\in V\}=m\).
It is shown that to determine \(\lambda(G,d)\), it suffices to study the case when \(d=1\) and the labelling is nonnegative integral-valued. Let \(\lambda(G)=\lambda(G,1)\). The labelling numbers of special classes of graphs, e.g., \(\lambda(C)=4\) for any cycle \(C\), are described. It is shown that for graphs of maximum degree \(\Delta\), \(\lambda(G)\leq \Delta^ 2+2\Delta\). If \(G\) has diameter 2, \(\lambda(G)\leq \Delta^ 2\), a sharp bound for some \(\Delta\). Determining \(\lambda(G)\) is shown to be NP-complete by relating it to the problem of finding Hamilton paths.