1 for n=2 3 for n=3 2n-4 for n>=4

This can be achieved as follows: choose four people (A, B, C, and D) as the "core group". Each person outside the core group phones a member of the core group (it doesn't matter which); this takes n-4 calls. Now the core group makes 4 calls: A-B, C-D, A-C, and B-D. At this point, each member of the core group knows everything. Now, each person outside the core group calls anybody who knows everything; this again requires n-4 calls, for a total of 2n-4.

The solution to the "gossip problem" has been published several times:

1. R. Tidjeman, "On a telephone problem", Nieuw Arch. Wisk. 3 (1971), 188-192.

2. B. Baker and R. Shostak, "Gossips and telephones", Discrete Math. 2 (1972), 191-193.

3. A. Hajnal, E. C. Milner, and E. Szemeredi, "A cure for the telephone disease", Canad Math. Bull 15 (1976), 447-450.

4. Kleitman and Shearer, Disc. Math. 30 (1980), 151-156.

5. R. T. Bumby, "A problem with telephones", Siam J. Disc. Meth. 2 (1981), 13-18.