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

Chartrand, Gary; Erwin, David; Zhang, Ping

Bull. Inst. Comb. Appl. 43, 43-57 (2005).

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.

Reviewer: Zsuzsanna Szaniszló (Valparaiso)

MSC:

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

Keywords:

radio labeling; radio number; channel assignment