Bounded depth broadcasting (Q1917294)

A broadcasting process with a bound on the number of retransmissions occurs, for example, where information degrades under repetition, or where photocopies do not retain the crispness of the original. The authors model such a process with graphs in which the depth of broadcast tree---spanning rooted trees originating at every vertex---cannot exceed \(d\); in any time unit each vertex that has been informed is permitted to communicate to at most one new vertex. The broadcast time of a graph \(G\) is the maximum of the broadcast times of all vertices \(u\); which, in turn, is the number of time units required, beginning at \(u\), to inform all vertices. The minimum broadcast time over all graphs \(G\) on \(n\) vertices is \(\pi_d(n)\); a graph \(G\) with broadcast time \(\tau_d(n)\) is called a broadcast graph. The minimum number of edges in a broadcast graph on \(n\) vertices is denoted by \(B_d(n)\); a graph attaining this minimum is a minimum broadcast graph. Conjecture 3.1: For any \(n\) and \(d\) there is a minimum broadcast graph with maximum degree \(\tau_d(n)\). ``Our main goal (\dots) is to develop methods for constructing good bounded depth broadcast graphs; we do this in Section 4. In Section 2 we exhibit a number of small optimal graphs, most of which are not produced by general constructions. In Section 3 we prove lower bounds on \(B_d(n)\).'' ``We present several general constructions that produce infinite families of optimal networks (minimum time and minimum number of [edges]). We also exhibit a number of small optimal networks that are not produced by the general construction''.