Let $G$ be a $\Delta$-regular graph on $n$ vertices. Is it possible to assign to each vertices a unique binary id (eventually very long) such that for every neighbour pair, the first digit on which they differ is as small as possible?
I assume $log_2(\Delta)$ is the best max-min we can do. If we don’t restrict to binary but with base $b$, probably $log_b(\Delta)$. However I’m not aware of such a result.
Note that I’m only looking for an existence result and not an algorithm.
Context: I’m working on distributed algorithms and I would like to use these IDs as a precomputation to speed up some other algorithms.
This is called graph bandwidth and the lower bound would be in that case $log_b(K-1)$ where $K$ is the chromatic number. I haven’t checked the proof but I guess it comes from the fact a non-unique ID assignment would certainly requires at least $K$ different ids