Radio labelling of two-branch trees
share
A radio labelling of a graph G is a mapping f : V(G) →{0, 1, 2,…} such that |f(u)-f(v)| ≥ diam(G) + 1 - d(u,v) for every pair of distinct vertices u,v of G, where diam(G) is the diameter of G and d(u,v) is the distance between u and v in G. The radio number rn(G) of G is the smallest integer k such that G admits a radio labelling f with max{f(v):v ∈ V(G)} = k. The weight of a tree T from a vertex v ∈ V(T) is the sum of the distances in T from v to all other vertices, and a vertex of T achieving the minimum weight is called a weight center of T. It is known that any tree has one or two weight centers. A tree is called a two-branch tree if the removal of all its weight centers results in a forest with exactly two components. In this paper we obtain a sharp lower bound for the radio number of two-branch trees which improves a known lower bound for general trees. We also give a necessary and sufficient condition for this improved lower bound to be achieved. Using these results, we determine the radio number of two families of level-wise regular two-branch trees.
READ FULL TEXT