On time-relaxed broadcasting networks Original Research Article

Given a communication network (modelled as a graph), a message is transmitted to at one vertex transmits to all other vertices in such a way that each message transmission takes one time unit and each vertex participates in at most one transmission to its neighbor per time step. We call this process broadcasting. For image, let image be the number of edges in the sparsest possible graph on image vertices in which broadcasting can be accomplished in image steps regardless of the originator. Shastri [A. Shastri, Time-relaxed broadcasting in communication networks, Discrete Applied mathematics 83 (1998) 263–278] conjectured that image and image for image. In this paper, we show that image, image for image and image, image for image, image for image, and image for image.