The Radio numbers of all graphs of order $n$ and diameter $n-2$

Abstract

A radio labeling of a connected graph $G$ is a function $c:V(G)\to {\mathbb{Z}}_{+}$ such that for every two distinct vertices $u$ and $v$ of $G$ $$\text{distance}(u,v)+|c(u)-c(v)|\ge 1+\text{diameter}(G).$$ The radio number of a graph $G$ is the smallest integer $M$ for which there exists a labeling $c$ with $c(v)\le M$ for all $v\in V(G)$. The radio number of graphs of order $n$ and diameter $n-1$, i.e., paths, was determined in \cite{paths}. Here we determine the radio numbers of all graphs of order $n$ and diameter $n-2$.

21 pages, 10 figures