More broadcast graphs

Given a graph G = (V, E) and a vertex u is an element of V, broadcasting is the process of disseminating a piece of information from vertex u to every other vertex in the graph where, in each time unit, any vertex which knows the information can pass the information to at most one of its neighbors. A broadcast graph on n vertices is a graph which allows any vertex to broad cast in time [log n]. A minimum broadcast graph on n vertices is a broadcas t graph with the minimum number of edges over all broadcast graphs on n ver tices. This minimum number of edges is denoted by B(n). Several papers have presented techniques to construct broadcast graphs for various n and, henc e, upper bounds on B(n). Ln this paper, we present new techniques to constr uct broadcast graphs that give improved upper bounds for 5417 values of it in the range 1 less than or equal to n less than or equal to 2(14) and for most values of n greater than or equal to 2(20). These graphs can be combin ed using some of the previous methods to produce further improvements. (C) 1999 Elsevier Science B.V. All rights reserved.