A Graph Labeling Problem Suggested by FM Channel Restrictions

Abstract

radio labeling of a connected graph G is an assignment c of distinct positive integers to the vertices of G such that d(u, v) + lc(u) - c(v)I ~ 1 + diam(G) for every two distinct vertices u , v of G, where d(u, v) denotes the distance between u and v and diam( G) is the diameter of G. The radio number rn (c) of a radio labeling 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.