A Problem with Telephones

Author:
  • RBRichard T. Bumby
    Richard T. Bumby

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.

This publication has 6 references indexed in Scilit: