Improved lower bounds for the radio number of trees (Q2220806)

This contribution fits inside the area of graph theory. For a graph \(G=(V,E)\) with diameter \(d\), let us denote by \(d(u,v)\) the distance (in \(G\)) between vertices \(u\) and \(v\). We then say that a radio labelling of \(G\) is a function \(f\) on vertices such that for all \(u,v \in V \) we have the relation \[| f (u) - f (v)|\geq d + 1 -d(u, v).\] The span of \(f\) is then the absolute difference of the largest and smallest values of the image of \(f\). Finally, the radio number of \(G\) is the minimum span of a radio labelling admitted by \(G\). The radio number for trees is a well studied problem: \textit{D. D. F. Liu} [Discrete Math. 308, No. 7, 1153--1164 (2008; Zbl 1133.05090)] obtained the following general lower bound: the radio number of a tree \(G\) is always greater or equal than \[(|V|-1)(d+1)+1-2W(G),\] where \(W(G)\) is the maximum value of \(W (x)=\sum_{y\in V} d(x,y)\) among all vertices \(x\) in \(V\). This is a very general bound, and the purpose of the paper is to strenghten it under extra conditions. More precisely, the authors study trees in the family \(\Omega_d^h\), which are the trees with a centroid of degree 2, height \(h\), and diameter \(d\). The main results in this paper (Theorem 10 and Theorem 15) obtain improvements on the radio number for trees in \(\Omega_d^h\). The techinques are elementary and arise from graph theory.