Broadcasting from multiple originators

We begin an investigation of broadcasting from multiple originators, a variant of broadcasting in which any kk vertices may be the originators of a message in a network of nn vertices. The requirement is that the message be distributed to all nn vertices in minimum time. A minimum  kk-originator broadcast graph   is a graph on nn vertices with the fewest edges such that any subset of kk vertices can broadcast in minimum time. Bk(n)Bk(n) is the number of edges in such a graph. In this paper, we present asymptotic upper and lower bounds on Bk(n)Bk(n). We also present an exact result for the case when k≥n2. 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.