The Radio Number of Standard Caterpillars

Abstract

A radio labeling of a connected graph \(G\) of diameter \(d\) is a mapping \(f: V(G) \to \{0, 1, 2, \ldots\}\) such that \(d(u, v) + |f(u) – f(v)| \geq d + 1\) for each pair of distinct vertices \(u\) and \(v\) of \(G\), where \(d(u, v)\) is the distance between \(u\) and \(v\). The value \(rn(f)\) of a radio labeling \(f\) is the maximum label assigned by \(f\) to a vertex of \(G\). The radio number \(rn(G)\) of \(G\) is the minimum value of \(rn(f)\) taken over all radio labelings \(f\) of \(G\). A caterpillar \(C_{m,t}\) is a special tree that consists of a path \(x_1x_2 \ldots x_m\) (\(m \geq 3\)), with some pendant vertices adjacent to the inner vertices \(x_2, x_3, \ldots, x_{m-1}\). If \(d(x_i) = t\) (the degree of \(x_i\)) for \(i = 2, 3, \ldots, m-1\), then the caterpillar is called standard. In this paper, we determine the exact value of the radio number of \(C_{m,t}\) for all integers \(m \geq 4\) and \(t \geq 2\), and explicitly construct an optimal radio labeling. Our results show that the radio number and the construction of optimal radio labeling of paths are special cases of \(C_{m,t}\) with \(t = 2\).