Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping, every
person in the network knows a unique item of information and needs to communicate
it to everyone else. In broadcasting, one individual has an item of information which
needs to be communicated to everyone else (Hedetniemi et al. 1988).

A popular formulation assumes there are people, each one of whom knows a scandal which is not known
to any of the others. They communicate by telephone, and whenever two people place
a call, they pass on to each other as many scandals as they know. How many calls
are needed before everyone knows about all the scandals? Denoting the scandal-spreaders
as , , ,
and , a solution for is given by , ,
, . The solution can then be generalized to by adding the pair to the beginning and end of the previous solution, i.e.,
, , ,
, , .

Gossiping (which is also called total exchange or all-to-all communication) was originally introduced in discrete mathematics as a combinatorial problem in graph
theory, but it also has applications in communications and distributed memory
multiprocessor systems (Bermond et al. 1998). Moreover, the gossip problem
is implicit in a large class of parallel computing
problems, such as linear system solving, the discrete
Fourier transform, and sorting. Surveys are given
in Hedetniemi et al. (1988) and Hromkovic et al. (1995).

Let be the number of minimum calls necessary
to complete gossiping among
people, where any pair of people may call each other. Then , , , and

for . This result was proved by (Tijdeman
1971), as well as many others.

In the case of one-way communication ("polarized telephones"), e.g., where communication is done by letters or telegrams, the graph becomes a directed
graph and the minimum number of calls becomes

Bermond, J.-C.; Gargano, L.; Rescigno, A. A.; and Vaccaro, U. "Fast Gossiping by Short Messages." SIAM J. Comput.27,
917-941, 1998.Harary, F. and Schwenk, A. J. "The Communication
Problem on Graphs and Digraphs." J. Franklin Inst.297, 491-495,
1974.Hedetniemi, S. M.; Hedetniemi, S. T.; and Liestman, A. L.
"A Survey of Gossiping and Broadcasting in Communication Networks." Networks18,
319-349, 1988.Hromkovic, J.; Klasing, R.; Monien, B.; and Peine, R.
"Dissemination of Information in Interconnection Networks (Broadcasting and
Gossiping)." In Combinatorial
Network Theory (Ed. F. Hsu and D.-A. Du). Norwell, MA: Kluwer,
pp. 125-212, 1995.Tijdeman, R. "On a Telephone Problem."
Nieuw Arch. Wisk.19, 188-192, 1971.