Fault‐tolerant broadcast graphs

Broadcasting refers to the process of information dissemination in a communications network whereby a message, originated by one member, is transmitted to all members of the network. By incorporating redundancy in the calling scheme, the completion of the broadcast may be guaranteed in the presence of up to k link failures. A k fault‐tolerant broadcast graph represents a network configuration which admits such a scheme. This article investigates these graphs and the tradeoff between the time allowed for broadcasting and the number of edges required in the graph.