Extremal problems on consecutive \(L(2,1)\)-labelling (Q2370429)

For a given graph \(G=(V,E)\) of order \(n\), a \(k\)-\(L(2,1)\)-labelling of \(G\) is defined as a function \(f: V \rightarrow \{0,1,\dots,k-1\}\) such that \(| f(u)-f(v)| \geq 2\) if the distance \(d_G(u,v)=1\) and \(| f(u)-f(v)| \geq 1\) if \(d_G(u,v)=2\). A consecutive \(k\)-\(L(2,1)\)-labelling is a \(k\)-\(L(2,1)\)-labelling with the additional condition that \(\{f(v): v \in V\}\) is a set of consecutive integers. The \(L(2,1)\)-labelling number \(\lambda(G)\) is defined to be the minimum number \(k\) such that \(G\) has a \(k\)-\(L(2,1)\)-labelling. Analogously, the consecutive \(L(2,1)\)-labelling number \(\overline\lambda(G)\) is defined to be the minimum number \(k\) such that \(G\) has a consecutive \(k\)-\(L(2,1)\)-labelling. Obviously, \(\lambda(G) \leq \overline\lambda(G) \leq | V| -1\). In this paper, the authors investigate the graphs \(G\) with \(\overline\lambda(G)=| V| -1\) and the graphs \(G\) with \(\overline\lambda(G)=\lambda(G)\) in terms of their sizes, diameters and the number of components.