Sparse broadcast graphs

AbstractBroadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Several previous papers have investigated ways to construct sparse graphs (networks) on n vertices in which this process can be completed in minimum time from any originator. In this paper, we describe four techniques to construct graphs of this type and show that they produce the sparsest known graphs for several values of n. For n = 18, n = 19, n = 30 and n = 31 we also show that our new graphs are minimum broadcast graphs (i.e., that no graph with fewer edges is possible). These new graphs can be used with other techniques to improve the best known results for many larger values of n