Construction of Minimum Time-Relaxed Broadcasting Communication Networks

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].