Minimum multiple message broadcast graphs
Hovhannes A. Harutyunyan · Networks · 2006
Abstract Multiple message broadcasting is the process of multiple message dissemination in a communication network in whichmmessages, originated by one vertex, are transmitted to all vertices of the network. A graphGwithnvertices is called a 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 onnvertices. An m‐message minimum broadcast graph is a broadcast graphGonnvertices havingBm(n) edges. This article presents several lower and upper bounds onBm(n). In particular, it is shown that modified Knödel graphs are m‐message broadcast graphs form≤ min⌊logn⌋,n− 2⌊logn⌋. From the Cartesian product of some broadcast graphs we obtain better upper bounds onBm(n), and in some cases we can prove thatBm(n) =O(n). The exact value ofB2(2k) is also established. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 218–224 2006