Radio Number for the Cartesian Product of Two Trees
share
Let G be a simple connected graph. For any two vertices u and v, let d(u,v) denote the distance between u and v in G, and let diam(G) denote the diameter of G. A radio-labeling of G is a function f which assigns to each vertex a non-negative integer (label) such that for every distinct vertices u and v in G, it holds that |f(u)-f(v)| ≥ diam(G) - d(u,v) +1. The span of f is the difference between the largest and smallest labels of f(V). The radio number of G, denoted by rn(G), is the smallest span of a radio labeling admitted by G. In this paper, we give a lower bound for the radio number of the Cartesian product of two trees. Moreover, we present three necessary and sufficient conditions, and three sufficient conditions for the product of two trees to achieve this bound. Applying these results, we determine the radio number of the Cartesian product of two stars as well as a path and a star.
READ FULL TEXT