Multi-broadcasting is the process of disseminating information in a network by placing a series of calls over the nodes in the network. Each call requires one unit of time and a node is allowed to call at most k of its adjacent nodes simultaneously. Following these constraints, at most (k + 1) t vertices can be informed in t time steps. Alternatively, the time taken to complete a k-broadcast on n vertices is ⌈log(k+1)n⌉. Multi-broadcasting has been extensively studied and some lower bounds for Bk(n), the number of edges in a minimum k-broadcast graph (kmbg) with n vertices, for k = 2, 3 & 4 have been presented for small n. We present some more values for B2 (n) for 13 ≤ n ≤ 16 with proofs of optimality and 2-broadcast schemes with different vertices as originators.

Broadcasting, Multi-broadcasting, Multi-broadcast Graphs, Communication Networks