Abstract

 

Informally, a radio labeling is a simplified, graph-theoretic model of FCC regulations governing the assignment of frequencies to commercial FM stations. Formally, a radio labeling of a connected graph G is an assignment of distinct positive integers to the vertices of G, with x labeled c(x), such that d(u,v) + |c(u)-c(v)| >= 1 + diam G for every two distinct vertices u,v of G. The radio number rn(c) of a radio labeling c of G is the maximum label assigned to a vertex of G. The radio number rn(G) of G is min{rn(c)} over all radio labelings c of G. I shall discuss the Channel Assignment Problem and some of the work that has been done on radio labelings. This is joint work with Gary Chartrand, Frank Harary and Ping Zhang.