Radio labelings of graphs. (English) Zbl 0989.05102

Chartrand, Gary; Erwin, David; Zhang, Ping; Harary, Frank

Bull. Inst. Comb. Appl. 33, 77-85 (2001).

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.

Reviewer: Fedor Fomin (Paderborn)

MSC:

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

Keywords:

radio coloring; radio labeling; radio number; characterization