Optimal \(L(d,1)\)-labelings of certain direct products of cycles and Cartesian products of cycles (Q2576352)

An \(L(d,1)\)-labeling of the vertex set \(V_G\) of a graph \(G\) is an assignment of nonnegative integers to the vertices so that the labels of every pair of adjacent vertices differ at least in \(d\) and those at distance 2 receive different labels. Let \(\lambda^d_1(G)\) denote the minimal \(\lambda\) for which there exists an \(L(d,1)\)-labeling that uses labels from the set \(\{0,1,\dots,\lambda\}\). It is shown that for \(d\geq 1\) and \(k\geq 2\), for the Cartesian product of cycles one has \(\lambda^d_1(C_{m_0}\times\cdots\times C_{m_{k-1}})\leq 2^k + 2d-2\) with equality if \(1\leq d\leq 2^k\). Similarly, for the direct product of cycles one has \(\lambda^d_1(C_{m_0}\otimes\cdots \otimes C_{m_{k-1}})\leq 2k+2d-2\) with equality if \(1\leq d\leq 2k\).