The construction of minimum broadcast graphs is extremely difficult; furthermore, even determining the broadcast time of a vertex in an arbitrary graph is known to be NP-complete. Due to this difficulty, much research is done on the construction of sparse broadcast graphs, which have a low number of edges, but not necessarily B(n). The construction of such graphs established upper bounds on the function B(n). Many techniques for construction these graphs exist; a sampling is presented here.
 

Farley's Method

This method comes from [3], and can be used to construct a broadcast graph on n vertices for arbitrary n, where n ¹ 2^k + 1 for any k. Let G₁ be a broadcast graph on n₁ vertices, and let G₂ be a broadcast graph on n₂ vertices, where n₁ + n₂ = n and n₁ ³ n₂. Add a matching involving n₂ edges between G₁ and G₂. Let u Î V(G₁) È V(G₂), and assume that u is the originator of a broadcast in G₁ È G₂. If u is on an edge of the matching, it first calls it's counterpart u', and these two vertices then complete broadcasting in G₁ and G₂; hence, broadcasting completes in max{élog₂n₁ù ,élog₂n₂ù} + 1 time units. If u is not on an edge in the matching, u must be in G₁, since n₁ ³ n₂. In this case, u first completes broadcasting in G₁; then, all vertices in G₁ which are on edges of the matching broadcast to their counterparts in G₂. Broadcasting thus completes in élog₂n₁ù + 1 time units. These are the only two possible cases.

In particular, if n₁ = n₂ or n₁ = n₂ + 1 and n₁ + n₂ ¹ 2^k + 1 for any k, broadcasting completes in élog₂n₁ù + 1 = élog₂n₁ + 1ù = élog₂n₁ + log₂2ù = élog₂2n₁ù = élog₂nù time units. The graph obtained by adding the matching between G₁ and G₂ is thus a broadcast graph.