A Problem with Telephones
Author:
- Richard T. BumbyRBRichard T. Bumby
- 1 March 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 2 (1) , 13-18
Abstract
This paper deals with the “telephone problem,” also known as the “gossip problem”. Suppose n persons each have a piece of information. Pairs of them can share whatever information they possess by making a telephone call. The question arises, what minimum number of calls allows all n persons to obtain all n pieces of information. The answer is $2n - 4$. One can then ask about properties of such minimal sets of calls. In particular, we prove that the graph whose edges are the calls must contain a four-cycle.
Keywords
This publication has 6 references indexed in Scilit:
- Further gossip problemsDiscrete Mathematics, 1980
- Monthly Research Problems, 1969-75The American Mathematical Monthly, 1975
- Efficiency of dissemination of information in one-way and two-way communication networksSystems Research and Behavioral Science, 1974
- The communication problem on graphs and digraphsJournal of the Franklin Institute, 1974
- A Cure for the Telephone DiseaseCanadian Mathematical Bulletin, 1972
- Gossips and telephonesDiscrete Mathematics, 1972