On gossiping with faulty telephone lines. (English) Zbl 0626.05033

In the well-known gossip problem, each of n gossips initially has a unique piece of information. The gossips can make a sequence of two-party telephone calls in which the two participants exchange every piece of information they have at the time of the call. The problem is to determine a minimum length sequence of telephone calls such that, by the end, everyone knows everyone else’s information. We consider K. A. Berman and M. Hawrylycz’s variation on this problem [ibid. 7, 13- 17 (1986; Zbl 0578.05059)]. They introduce the additional feature that as many as k of the calls may fail in the sense that no information is exchanged, where k is a second parameter of the problem. We improve upon their upper bound on the minimum number of calls needed. This disproves a conjecture in the same paper. We also briefly consider the parallel complexity of this problem.


05C38 Paths and cycles
94C15 Applications of graph theory to circuits and networks


Zbl 0578.05059
Full Text: DOI


[1] Baker, Brenda; Shostak, Robert, Gossips and telephones, Discrete Math., 2, 191, (1972) · Zbl 0245.05002
[2] Berman, KennethA.; Hawrylycz, Michael, Telephone problems with failures, SIAM J. Algebraic Discrete Methods, 7, 13, (1986) · Zbl 0578.05059
[3] Bumby, RichardT., A problem with telephones, SIAM J. Algebraic Discrete Methods, 2, 13, (1981) · Zbl 0499.05034
[4] Hajnal, A.; Milner, E. C.; Szemerédi, E., A cure for the telephone disease, Canad. Math. Bull., 15, 447, (1972) · Zbl 0251.05132
[5] Knödel, Walter, New gossips and telephones, Discrete Math., 13, 95, (1975) · Zbl 0305.05001
[6] Liestman, ArthurL.; Richards, Dana, Toward optimal gossiping schemes with conference calls, Discrete Appl. Math., 7, 183, (1984) · Zbl 0529.05043
[7] Seress, Ákos, Gossiping old ladies, Discrete Math., 46, 75, (1983) · Zbl 0518.05001
[8] Tijdeman, R., On a telephone problem, Nieuw Arch. Wisk. (3), 19, 188, (1971) · Zbl 0226.05001
[9] West, DouglasB., A class of solutions to the gossip problem. I, Discrete Math., 39, 307, (1982) · Zbl 0497.05037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.