A study of minimum gossip graphs

AbstractGossiping and broadcasting are two problems of information dissemination described in a group of individuals connected by a communication network. In broadcasting, one individual has an item of information and needs to communicate it to everyone else. In gossiping, every person in the network knows a unique item of information and needs to communicate it to everyone else. Those two communication patterns find their main applications in the field of interconnection networks for parallel and distributed architecture. After reviewing some of the main results that have been obtained on these problems, we give new properties concerning gossiping, mainly about the structure of the networks with n nodes gossiping in minimum time and their minimum number, G(n), of communication links. These properties lead to new bounds for G(n) in the general case, and in particular when 1⩽n⩽32. Moreover, for some values of n (namely n=15,24,28), we show the exact value of G(n)