Radio Number

Let G be a finite, connected, undirected graph with graph diameter d(G) and graph distance d(u,v) between vertices u and v. A radio labeling of a graph G is labeling using distinct nonnegative integers such that |f(u)-f(v)|>=d(G)+1-d(u,v) for every pair of distinct vertices u, v in the vertex set of G. Then the radio number of G, commonly denoted rn(G), is the smallest integer k such that G has a radio labeling f with max{f(v):v in V(G)}=k.

The radio number of path graphs P_n and cycle graphs C_n were determined by Liu and Zhu (2005). The following table summarizes some known results for a number of special families of graphs.

See also

Graph Diameter, Graph Distance

Explore with Wolfram|Alpha


Bantva, D. "Further Results on the Radio Number of Trees." 25 May 2018., G.; Erwin, D.; Harary, F.; and Zhang, P. "Radio Labelings of Graphs." Bull. Inst. Combin. Appl. 33, 77-85, 2001.Chartrand G.; and Zhang, P. "Radio Colorings of Graphs--A Survey." Int. J. Comput. Appl. Math. 2, 237-252, 2007.Griggs, J. R. and Yeh, R. K. "Labeling Graphs with Condition at Distance. 2." SIAM J. Disc. Math. 5, 586-595, 1992.Liu, D. "Radio Number for Trees." Disc. Math. 308, 1153-1164, 2008.Liu, D. D.-F.; Zhu, X. "Multilevel Distance Labelings for Paths and Cycles." SIAM J. Disc. Math. 19, 610-621, 2005.Zhang, P. "Radio Labeling of Cycles." Ars Combin. 65, 21-32, 2002.

Cite this as:

Weisstein, Eric W. "Radio Number." From MathWorld--A Wolfram Web Resource.

Subject classifications