k-broadcasting is a generalization of classical broadcasting in which an informed vertex can call up to k neighbours during each time unit. Classical broadcasting is thus a special case of k-broadcasting in which k = 1.

The k-broadcast time of vertex u in V(G) for a graph G on n vertices, denoted b_k(u), is the minimum number of time units required to complete k-broadcasting in G with u as the originator. Since the number of informed vertices can, at most, be multiplied by k + 1 during each time unit, b_k(u) ³ élog_{k + 1}nù. The k-broadcast time of G, denoted b_k(G), is defined as b_k(G) = max{b_k(u) | u Î V(G) }. A graph G on n vertices for which b_k(G) = élog_{k + 1}nù is called a k-broadcast graph. The complete graph K_n is a k-broadcast graph, but it has many more edges than necessary for all n ³ 4 when n ³ k + 2. We denote the minimum number of edges necessary in a k-broadcast graph on n vertices by B_k(n). We call a k-broadcast graph on B_k(n) vertices a minimum k-broadcast graph.