Multiple message broadcasting is the process of multiple message dissemination in a communication network in which m messages, originated by one vertex, are transmitted to all vertices of the network. A graph G with n vertices is called an m-message broadcast graph if its broadcast time is the theoretical minimum. Bm(n) is the minimum number of edges in any m-message broadcast graph on n vertices. An m-message minimum broadcast graph is a broadcast graph G on n vertices having Bm(n) edges. This article presents several lower and upper bounds on Bm(n). In particular, it is shown that modified Knödel graphs are m-message broadcast graphs for m ≤ min(⌊log n⌋,n − 2⌊log n⌋). From the Cartesian product of some broadcast graphs we obtain better upper bounds on Bm(n), and in some cases we can prove that Bm(n) = O(n). The exact value of B2(2k) is also established.
