NOTE ON OPTIMAL GOSSIPING IN SOME WEAK-CONNECTED GRAPHS

The problems of gossiping and broadcasting in one-way communication mo de are investigated. Optimal algorithms for gossip problem are known o nly for the complete graphs, paths, some simple trees, and cycles. In this paper some lower bounds on gossiping in graphs with bridges or wi th edge disjoint cycles are proved. A direct consequence of these lowe r bounds is the construction of optimal gossip algorithms for some fam ilies of weak-connected graphs. Another question considered here is th e relationship between the gossip problem and the broadcast problem. G ossiping cannot be more than twice as hard as broadcasting, and only f or trees it is known that gossiping is exactly two times harder than b roadcasting. Using the above-mentioned lower bounds some other graphs (having cycles) with this property are found.