Adjacent -- let u,v Î V(G). u is adjacent to v iff there is an edge between u and v.

B(n) -- the minimum number of edges in a broadcast graph on n vertices.

Broadcasting -- an information dissemination problem in which one vertex in a graph, called the originator, must distribute a message to all other vertices by placing a series of calls along the edges of the graph. Once informed, other vertices aid the originator in distributing the message. This is assumed to take place in discrete time units.

Broadcast Graph -- a graph in which broadcasting can be accomplished in élog₂nù time units.

Cartesian product (´) -- let G₁ = (V₁, E₁) and G₂ = (V₂, E₂), where G₁ is a graph on n₁ vertices, and G₂ is a graph on n₂ vertices. Then G₁ ´ G₂ is a graph on n₁n₂ vertices, where V(G₁ ´ G₂) = V(G₁) ´ V(G₂), and (v₁,u₁) is connected to (v₂,u₂) if v₁ = v₂ and u₁ is adjacent to u₂, or u₁ = u₂ and v₁ is adjacent to v₂.

Degree -- let u Î V(G). The degree of u, denoted deg(u), is the number of vertices to which u is adjacent. The degree of G, denoted deg(G), is max{deg(u) | u Î V(G)}.

Diameter -- the maximum distance between any two vertices in a graph G.

Distance -- let u, v Î V(G). The distance between u and v is the length of the shortest path between u and v.

Graph -- a pair G = (V, E), where G is a set of vertices, and E is a set of pairs of vertices or edges. In broadcasting, the vertices typically represent computers, and the edges wires between computers; however, graphs can be applied to a multitude of other problems as well.

Hypercube -- denoted Q_k, is a k-dimensional cube. Formally, Q₁ = K₂, and Q_k = Q_k-1 ´ K₂ (´ is the Cartesian product operation). Hypercubes are the most famous of the only two known classes of minimum broadcast graphs.

Matching -- a set of edges, in which no two edges have a common vertex.

Minimal broadcast graph -- a broadcast graph of which no spanning proper subset is a broadcast graph.

Minimum broadcast graph -- a broadcast graph having B(n) edges.

Path -- let u, v Î V(G). A path between u and v is a sequence of vertices u = v₀, v₁, . . ., v_n = v, such that v_i ¹v_j for all i, j, and v_i is adjacent to v_i-1, for 1 £ i £n.