Given a graph  G =( V , E ) and a vertex  u ∈ 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 broadcast in time        . A  minimum broadcast graph  on  n  vertices is a broadcast graph with the minimum number of edges over all broadcast graphs on  n  vertices. This minimum number of edges is denoted by  B ( n ). Several papers have presented techniques to construct broadcast graphs for various  n  and, hence, upper bounds on  B ( n ). In this paper, we present new techniques to construct broadcast graphs that give improved upper bounds for 5417 values of  n  in the range 1⩽ n ⩽2 14  and for most values of  n ⩾2 20 . These graphs can be combined using some of the previous methods to produce further improvements.
['Hovhannes A. Harutyunyan', 'Arthur L. Liestman']
More broadcast graphs