Compounding of gossip graphs
Guillaume Fertin, Roger Labahn · Networks · 2000
Gossiping refers to the following task: In a group of individuals connected by a communication network, every node has a piece of information and needs to transmit it to all the nodes in the network. The networks are modeled by graphs, where the vertices represent the nodes, and the edges, the communication links. In this paper, we concentrate on minimum 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 [Networks 9 (1979), 313–332]. 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 [5]. We also show that, when applicable, this method gives the best-known upper bounds on the size of minimum gossip graphs in most cases, either improving or matching them. Notably, we present for the first time two families of regular gossip graphs of order n and of degree ⌈log2(n)⌉ − 3 and ⌈log2(n)⌉ − 4, respectively. We also give some lower bounds on the number of edges of gossip graphs which improve the ones given by Fertin [5]. Moreover, we show that the above compounding method also applies for minimum linear gossip graphs (or MLGGs) of even order, which corresponds to a variant of gossiping where the time of information transmission between two nodes depends on the amount of information exchanged. We also prove that this gives the best-known upper bounds for Gβ,τ(n)—the size of an MLGG of order n—in most cases. In particular, we derive from this method the exact value of Gβ,τ(72), which was previously unknown. © 2000 John Wiley & Sons, Inc.