A Minimum Broadcast Graph on 63 Vertices

We describe the construction of a minimum broadcast graph with 63 vertices. The graph has 162 edges. Part of this work was done while the author visited the School of Computing Science at Simon Fraser University, Burnaby B.C. Canada. 1. Introduction Let G = (V; E) be a graph with n vertices and v 2 V be any vertex. Broadcasting is the process of disseminating an item of information generated at v to every other vertex of G where in every step or round, each vertex already knowing that item passes it to one of its neighbors. It is easy to see that it takes at least dlog 2 ne rounds until every vertex of the graph knows v's information. We call G broadcast graph if for every vertex v 2 V , broadcasting can be completed in dlog 2 ne rounds. For all n, broadcast graphs exist, take the complete graph Kn as an example. Therefore, we may ask for the minimum number, B(n), of edges a broadcast graph on n vertices must have. A broadcast graph G = (V; E) with jV j = n and jEj = B(n) is..