Radio labelings of graphs. (English) Zbl 0989.05102

The authors the define radio labeling of a connected graph \(G=(V,E)\) as assignment \(c\) of distinct positive integers to the vertices of \(G\), such that \(d(u,v)+|c(u)-c(v)|\geq 1+\text{diam}(G)\) for every two distinct vertices \(u,v\in V\). (\(\text{dist}(u,v)\) is the distance between \(u\) and \(v\), and \(\text{diam}(G)\) is the diameter of \(G\).) The authors study the radio labeling problem on some graph classes. They provide some results for cycles and prove several results concerning connected graphs of diameter 2.


05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs