Hypercubes were the first infinite class of minimum broadcast graphs to be discovered. The hypercube Q_k has 2^k vertices. Farley et al. proved that B(2^k) = k·2^k-1 in [4].

To show that B(2^k) ³k·2^k-1, observe that every vertex in a minimum broadcast graph on 2^k vertices must have degree greater than or equal to k in order to call all 2^k vertices in k time units. Since S_"uÎV(G)deg(u) = 2e, where e is the number of edges in G, B(2^k) ³ k·2^k-1.

We can show that B(2^k) £k·2^k-1 by constructing a broadcast graph on 2^k vertices with k·2^k-1 edges. This can be done by adding a matching involving 2^k-1 edges to the union of two graphs on 2^k-1 vertices. This can be done inductively, starting with the minimum broadcast graph on 1 vertex.

Hypercubes satisfy the above conditions. To describe the hypercube broadcast scheme, assign k-bit binary labels 000...0 through 111...1 to the 2^k vertices of Q_k. Let u, v Î V(Q_k). u is adjacent to v iff the ith bit of u is different from the ith bit of v, and all other bits in their labels match. u and v are then called ith-dimensional neighbours. Broadcasting is accomplished as follows: at time i, 1 £ i £ k, all informed vertices broadcast to their ith-dimensional neighbours.