Broadcasting from multiple originators Original Research Article

We begin an investigation of broadcasting from multiple originators, a variant of broadcasting in which any image vertices may be the originators of a message in a network of image vertices. The requirement is that the message be distributed to all image vertices in minimum time. A minimum image-originator broadcast graph is a graph on image vertices with the fewest edges such that any subset of image vertices can broadcast in minimum time. image is the number of edges in such a graph. In this paper, we present asymptotic upper and lower bounds on image. We also present an exact result for the case when image. We also give an upper bound on the number of edges in a relaxed version of this problem in which one additional time unit is allowed for the broadcast.