Given a finite graph $G = (V,E)$ let $F$ be the set of all functions $f : v \to \mathbb{N}$ where $$\#(\{\lvert f(a) - f(b)\rvert \mid (a,b)\in E\})=\#(E)$$ (i.e., vertex mappings where the differences of vertex values connected by edges are all different). Let $$R = \min_f \max_v f(v).$$
Finding a minimal $f$ is considered to be a very difficult problem computationally for some families of graphs. For example, for the family of complete graphs it appears to me to be equivalent to the problem of finding optimal Golomb rulers. For other families, it is much easier or even trivial (e.g., path graphs, star graphs, cycles).
I ask the following questions:
- Is this problem known in the literature?
- Are there known algorithms for finding $R$ and the corresponding $f$ given a graph $G$ (possibly restricted to a given family, besides the four families noted above)?
- Besides the trivial bound that $R$ for a graph on $n$ vertices cannot be greater than the value of $R$ for the complete graph $K_n$ (nor smaller than one less than the number of edges in the graph), are any results known which give bounds on $R$?
Results for simple graphs
For cycles of size $n$, $$R(n) = \begin{cases} n-1, & n\equiv 0,1\pmod 4 \\ n, & n\equiv 2,3\pmod 4 \\ \end{cases}$$