2016/09/10 by Devsi Bantva, Bantva, Devsi, Samir Vaidya +3
Mathematics · #05C15 #05C78 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C78
paper · pdf · doi:10.48550/arxiv.1609.03002
19 pages, 7 figures. This is the final version accepted in Discrete Applied Mathematics
arxiv created 2016/09/10 · arxiv updated 2016/09/13
A radio labeling of a graph G is a mapping f: V(G) → \0, 1, 2, …\ such that |f(u)-f(v)|≥ d + 1 - d(u,v) for every pair of distinct vertices u, v of G, where d is the diameter of G and d(u,v) the distance between u and v in G. The radio number of G is the smallest integer k such that G has a radio labeling f with max\f(v) : v ∈ V(G)\ = k. We give a necessary and sufficient condition for a lower bound on the radio number of trees to be achieved, two other sufficient conditions for the same bound to be achieved by a tree, and an upper bound on the radio number of trees. Using these, we determine the radio number for three families of trees.