Broadcasting in DMA-bound bounded degree graphs

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Bermond, Hell, Liestman and Peters studied the effect, on broadcasting capabilities, of placing an upper bound on the graph’s degree. This paper generalizes their results by allowing calls to involve more than two participants. It gives lower bounds and constructs bounded degree graphs which allow rapid broadcasting. The present constructions use the notion of compounding graphs in de Bruijn digraphs. The paper also obtains asymptotic upper and lower bounds for broadcast time, as the maximum degree increases.