Distance-two labelings of graphs (Q1869030)

A labeling of the vertex set of a graph \(G=(V,E)\) is a mapping \(L: V \rightarrow \{0,1,2,\dots\}\). A labeling \(L\) is called \(L(j,k)\)-labeling, \(j\geq k\), if for any \(\{u,v\} \in E\), \(|L(u)-L(v)|\geq j\) and for any \(u,v\in V \) that are at distance \(2\) in \(G\), \(|L(u)-L(v)|\geq k\). The \(L(j,k)\)-labeling number \(\lambda_{j,k}(G)\) of \(G\) is the minimum \(m\) such that there is an \(L(j,k)\)-labeling \(L\) of \(G\) such that for any \(v\in V\), \(L(v)\leq m\). It is easy to prove that for a graph \(G\) of maximum degree \(\Delta\geq 1 \), \(\lambda_{j,k}(G)\geq j + (\Delta -1)k\). The paper studies the structures of graphs \(G\) with \(\lambda_{j,k}(G)= j + (\Delta -1)k\).