Consider a broadcast scheme on a connected graph from an originator vertex in a graph consisting of a sequence of parallel calls starting from . In each time step, every informed node (sender) can call at most one uninformed neighbor (receiver), corresponding to a directed edge. The process is iterated until every vertex in the network is informed, with the result being a directed spanning tree of rooted at called the broadcast tree of originator .
The minimum number of time steps required to broadcast from to all vertices in the graph is called the broadcast time of vertex , denoted . The maximum broadcast time over all originator vertices in is called the broadcast time of , denoted (Harutyunyan1 and Li 2019).
The broadcast time of a disconnected graph is the maximum of the broadcast times of its connected components.