Construction of Minimum Time-Relaxed Broadcasting Communication Networks

Abstract

A broadcast graph on $n$ vertices is a network in which a message can be broadcast in minimum possible ($=\lceil {\log }_{2}n\rceil$) time from any vertex. Broadcast graphs which have the smallest number of edges are called \emph{Minimum Broadcast Graphs}, and are subjects of intensive study. In this paper, we study how the number of edges in minimum broadcast graphs decreases, as we allow additional time over $\lceil {\log }_{2}n\rceil$.

We improve results obtained by Shastri in [15] and prove a conjecture posed by Shastri in [15, 16].