Guillaume Fertin, Roger Labahn
Compounding of Gossip Graphs
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock
94A05 Communication theory, See also {60G35, 90B12}
05C35 Extremal problems, See also {90C35}
Abstract: 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 {\em
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 {\em $k$-way split method}, previously introduced for
broadcasting by FARLEY. We show that this method can be
applied to gossiping in some cases, and that this
generalizes some compounding methods for gossip graphs given
given earlier by FERTIN. 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 improving or
matching them. Notably, we present for the first time two
infinite families of Gossip Graphs of respective degree
$\lceil\log_{2}(n)\rceil -3$ and $\lceil\log_{2}(n)\rceil
-4$. We also give some lower bounds on the number of edges
of Gossip Graphs which improve those given by FERTIN
\indent Moreover, we show that the above compounding method
also applies for {\em Minimum Linear Gossip Graphs} (or
$MLGG$s) of even order, which corresponds to a variant of
gossiping where the time of information transmission between
two nodes depends on the amount of the information
exchanged. We also prove that this gives the best known
upper bounds for $G_{\beta,\tau}(n)$ - the size of a $MLGG$
of order $n$ - in most cases. In particular, we derive from
this method the exact value of $G_{\beta,\tau}(72)$, which
was previously unknown.

Keywords: networks, communication, gossiping, minimum gossip graphs, minimum linear gossip graphs