Broadcasting in Highly Connected Graphs

Abstract

   Throughout history, spreading information has been an important task. With computer networks expanding, fast and reliable dissemination of messages became a problem of interest for computer scientists. Broadcasting is one category of information dissemination that transmits a message from a single originator to all members of the network. In the past five decades the problem has been studied by many researchers and all have come to demonstrate that despite its easy definition, the problem of broadcasting does not have trivial properties and symmetries. For general graphs, and even for some very restricted classes of graphs, the question of finding the broadcast time and scheme remains NP-hard. This work uses graph theoretical concepts to explore mathematical bounds on how fast information can be broadcast in a network. The connectivity of a graph is a measure to assess how separable the graph is, or in other words how many machines in a network will have to fail to disrupt communication between all machines in the network.

We initiate the study of finding upper bounds on broadcast time b(G) in highly connected graphs. In particular, we give upper bounds on b(G) for k-connected graphs and graphs with a large minimum degree.

We explore 2-connected (biconnected) graphs and broadcasting in them. Using Whitney’s open ear decomposition in an inductive proof we propose broadcast schemes that achieve an upper bound of ⌈n/2⌉ for classical broadcasting as well as similar bounds for multiple originators. Exploring further, we use a matching-based approach to prove an upper bound of ⌈log k⌉ + ⌈n/k ⌉ − 1 for all k -connected graphs. For many infinite families of graphs, these bounds are tight.

Discussion of broadcasting in highly connected graphs leads to an exploration of dependence between the minimum degree in the graph and the broadcast time of the latter. By using similar techniques and arguments we show that if all vertices of the graph are neighboring linear numbers of vertices, then information dissemination in the graph can be achieved in ⌈log h⌉ + C time.

To the best of our knowledge, the bounds presented in our work are a novelty. Methods and questions proposed in this thesis open new pathways for research in broadcasting.