Premium
Compounding of gossip graphs
Author(s) -
Fertin Guillaume,
Labahn Roger
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200009)36:2<126::aid-net8>3.0.co;2-3
Subject(s) - gossip , upper and lower bounds , computer science , combinatorics , node (physics) , broadcasting (networking) , mathematics , discrete mathematics , computer network , psychology , mathematical analysis , social psychology , structural engineering , engineering
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 ⌈log 2 ( n )⌉ − 3 and ⌈log 2 ( 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.