Broadcasting in Harary-Like Graphs

Broadcasting is an information dissemination problem in a connected graph in which one vertex, called the originator, must distribute a message to all other vertices by placing a series of calls along the edges of the graph. Every time the informed vertices aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. In this paper we consider the broadcast problem in Harary Graph, Hk, n which was first introduced by Frank Harary. Hk, n is a minimal k-connected graph on n vertices. We present a logarithmic additive approximation to find the broadcast time in an arbitrary Harary graph. For even values of n we also introduce a modified-Harary graph and present a 1-additive approximation algorithm to find the broadcast time. We show the optimality of our algorithm for a particular subclass of modified-Harary graph. Then we also show that modified-Harary graph is a broadcast graph when k is logarithmic of n.