A graph labeling problem suggested by FM channel restrictions. (English) Zbl 1066.05125

A radio labeling of a connected graph \(G\) is an assignment of \(c\) distinct positive integers to the vertices of \(G\) such that for any two distinct vertices, \(u\), \(v\), \(d(u, v)+|c(u)- c(v)|\geq1+ \operatorname{diam}(G)\), where \(d(u, v)\) denotes the distance of \(u\) and \(v\), and \(\text{diam}(G)\) is the diameter of \(G\). The radio number of \(G\) is the minimum of the largest label occurring over all radio labelings of \(G\). Bounds on radio numbers of graphs are presented in terms of diameter and other invariants. The radio numbers of paths are discussed in detail.


05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C12 Distance in graphs