Minimum Average Broadcast Time in a Graph of Bounded Degree

Broadcasting in a network is the process whereby information, initially held by one node, is disseminated to all nodes in the network. It is assumed that, in each unit of time, every vertex that has the information can send it to at most one of its neighbours that does not yet have the information. Furthermore, the networks considered here are of bounded (maximum) degree \(\Delta\), meaning that each node has at most \(\Delta\) neighbours. In this article, a new parameter, the average broadcast time, defined as the minimum mean time at which a node in the network first receives the information, is introduced. It is found that when the broadcast time is much greater than the maximum degree, the average broadcast time is (approximately) between one and two time units less than the total broadcast time if the maximum degree is at least three.