Minimum multiple message broadcast graphs

✍ Scribed by Hovhannes A. Harutyunyan

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 207 KB
• Volume: 47
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.20110

✦ Synopsis

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 a m-message broadcast graph if its broadcast time is the theoretical minimum. B m (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 B m (n) edges. This article presents several lower and upper bounds on B m (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 B m (n), and in some cases we can prove that B m (n) = O(n). The exact value of B 2 (2 k ) is also established.