Labelling graphs with the circular difference
For positive integers \(k\) and \(d\geq 2\), a \(k\)-\(S(d,1)\)-labelling of a graph \(G\) is a function on the vertex set of \(G\), \(f: V(G)\to \{ 0,1,2,\dots ,k-1\} \), such that \[ |f(u)-f(v)|_k\geq \left\{\begin{matrix} d &\text{if} {d} _G(u,v)=1 \\ 1 &\text{if} {d} _G(u,v)=2\end{matrix}\right. \] where \(|x|_k=\min\{ |x|,k-|x|\} \) is the circular difference modulo \(k\). The \(\sigma _d\)-number of \(G\), \(\sigma _d(G)\), is the minimum \(k\) for which a \(k\)-\(S(d,1)\)-labelling of \(G\) exists and \(\sigma_d'd(G)\) is the minimum \(k\) for which an injective \(k\)-\(S'(d,1)\)-labelling of \(G\) exists. If the circular difference is replaced by the absolute difference, then \(f\) is an \(L(d,1)\)-labelling of \(G\). The span of an \(L(d,1)\)-labelling is the difference of the maximum and minimum labels used. The \(\lambda _d\)-number of \(G\), \(\lambda _d(G)\), is the minimum span among all \(L(d,1)\)-labellings of \(G\). A lower and an upper bound for \(\sigma _d(G)\) in terms of \(\lambda _d(G)\) is determined. The values of \(\sigma _d(G)\) for trees and cycles are also determined. Furthermore, the values of \(\sigma_d'(G)\) for joins of graphs and for complete multipartite graphs are determined.
scientific article; zbMATH DE number 1547612