| Description: |
Gossiping refers to the problem of information dissemination described in a group of individuals connected by a communication network, whereby every node has a piece of information and needs to transmit it to all the nodes in the network. The networks are modelled by graphs, where the vertices represent the nodes, and the edges the communication links. In this paper, we concentrate on Minimum (Linear) Gossip Graphs of even order, that is graphs able to achieve gossiping in minimum time, and with a minimum number of links. More precisely, we derive upper bounds for their number of edges from a compounding method, the k-way split method, previously introduced for broadcasting by Farley [Far79]. We show that this method can be applied to gossiping in some cases, and that this generalizes some compounding methods for gossip graphs given in [Fer97]. We also show that, when applicable, this method gives the best known upper bound on the size of Minimum Gossip Graphs in most cases, either imp. |