Gossip graph

Gossip graph --- граф распространения слухов.

(See Gossiping problem). Let us consider a full-duplex model. Let [math]\displaystyle{ g(G) }[/math] be the time to gossip in a graph [math]\displaystyle{ G }[/math]. It is known that for the complete graph [math]\displaystyle{ K_{n} }[/math] we have:

--- [math]\displaystyle{ g(K_{n}) = \lceil\log_{2}(n)\rceil }[/math] for any even [math]\displaystyle{ n }[/math];

--- [math]\displaystyle{ g(K_{n}) = \lceil\log_{2}(n)\rceil + 1 }[/math] for any odd [math]\displaystyle{ n }[/math].

Any graph [math]\displaystyle{ G }[/math], such that [math]\displaystyle{ g(G) = g(K_{n}) }[/math], is called a gossip graph.

We call a minimum gossip graph of order [math]\displaystyle{ n }[/math] any gossip graph with a minimum number of edges. This number is denoted by [math]\displaystyle{ G(n) }[/math].