Radio Labelings of Cycles

Abstract

A radio labeling of a connected graph $G$ is an assignment of distinct, positive integers to the vertices of \(G\), with \(x \in V(G)\) labeled \(c(x)\), such that

\[d(u, v) + |c(u) – c(v)| \geq 1 + diam(G)\]

for every two distinct vertices \(u,v\) of \(G\), where \(diam(G)\) is the diameter of \(G\). The radio number \(rn(c)\) of a radio labeling \(c\) of \(G\) is the maximum label assigned to a vertex of \(G\). The radio number \(rn(G)\) of \(G\) is \(\min\{rn(c)\}\) over all radio labelings \(c\) of \(G\). Radio numbers of cycles are discussed and upper and lower bounds are presented.