Lower Bounds on Broadcast Function for n = 23, 24 and 25

The exponential growth of interconnection networks transformed the communication process into an important area of research. One of the fundamental types of communications is one-to-all communication, i.e. broadcasting. Broadcasting is an information dissemination process, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. One of the main problems in broadcasting is the minimum broadcast graph problem. Minimum broadcast graphs are the sparsest possible networks of this type, which have the minimum number of communication lines denoted by B(n) where n is the number of nodes in networks. Until now, B(n) is known only for a few general broadcast graph families and for some particular, mostly small values of n. For all n ¿ 32 B(n) is known, except for n = 23, 24 and 25. These cases were subject of our study. We introduce the case-by-case analysis of each of these graphs in order to determine the lower bound on B(n). Our results improved previously known lower bounds and can be used in future studies to construct minimum broadcast networks on 23, 24 and 25 nodes.