A survey on labeling graphs with a condition at distance two (Q2497501): Difference between revisions

If \(k\), \(d_{1}\), \(d_{2}\) are positive integers, a \(k\)-\(L\left(d_{1}, d_{2}\right)\) labeling of a graph \(G\) is a function mapping the vertices to \(\{0,1,\dots,k\}\) in such a way that the distance between the labels of \(u\) and \(v\) is \(\geq d_{i}\) whenever \(d_{G}(u,v)=i\) for \(i=1,2\). The \(L\left(d_{1}, d_{2}\right)\)-number of \(G\) is the smallest \(k\) such that there exists such a labeling. The study of these labelings was motivated by radio-frequency assignment problems. This paper surveys all important results in the area, most of which consist of calculating (bounds on) the \(L\left(d_{1}, d_{2}\right)\) number for various families of graphs. No proofs are included, so it is a necessary but not sufficient resource for beginners in the area. For experts it will serve as an essential summary of the state of the art.