The Gossip Problem: There are n ladies, and each of them knows some item of gossip not known to the others. They communicate by telephone, and whenever one lady calls another, they tell each other all that they know at that time. How many calls are required before each gossip knows everything? Solution: [Baker; Shostak], [Bumby], [Hajnal; Milner; Szemerédi] and [Tijdeman] showed with different methods that 2n - 4 calls are needed for n>=4. The proof of optimality is difficult and takes at least a page. With two additional calls a further gossip can participate. But n = 4 is critical, where one call can be saved. n=4: A---1---D The four ladies are A, B, C, and D. | | 3 4 The edges 1 to 4 give the calls in this order. | | B---2---C [Lebensold] generalized the problem for telephone conferences of k persons. This proof was simplified by [Kleitman, Shearer]. % - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - References: - Brenda Baker, Robert Shostak; Gossips and Telephones, Discrete Mathematics 2 (1972) 191-193 MR 46 # 68 - Gerald Berman; The Gossip problem, Discrete Mathematics 4 (1973) 91 (Corrigendum p397) MR 46 # 7037 - J.-C. Bermond; Le problème des "ouvroirs". (French. English summary) Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 31--34, Colloq. Internat. CNRS, 260, CNRS, Paris, 1978. MR 81c:05056 - Richard T. Bumby; A problem with telephones, SIAM J. Alg. Disc. Meth. 2 (1981) 13-18 MR 82f:05083 (mailto:bumby@math.rutgers.edu) - Hajnal, A.; Milner, E. C.; Szemerédi, E. ; A cure for the telephone disease. Canad. Math. Bull. 15 (1972), 447--450. MR 47 #3184 - F. Harary; B. Raghavachari; The E-mail Gossip Number and the connected Domination Number, Appl. Math. Letter 10:4 (1997) 15-17 - e-mail can be sent to all neighbors of a vertex in one step. Let eg(G) be the minimal number of e-mails to be sent. 1) eg(K_n) = n, as any sending sequence of all n nodes will do. 2) eg(C_n) = 2n-3, using the sending node sequence 1,2...n,1,2...n-3 - D. J. Kleitman, J. B. Shearer; Further Gossip Problems, Discrete Mathematics 30 (1980) 151-156 MR 81d:05068 - R. Labahn; Kermels of minimum size gossip schemes, Discrete Mathematics 143 (1995) 99-139 - Kenneth Lebensold; Efficient communication by phone calls, Studies in Appl. Math. 52 (1973) 345-358 MR 49 #4797 - Tijdeman, R. ; On a telephone problem. Nieuw Arch. Wisk. (3) 19 (1971), 188-192. MR 49 #7151 - Ioan Tomescu; Introduction to Combinatorics, - The gossip problem (Baker, Shostak and Hajnal, Milner, Szemerdi, 1972) There are n gossips each of whom knows some gossip not known to the others. They communicate by telephone, and whenever one gossip calls another, they tell each other all they know at that time. Prove that the minimum number of calls required before each gossip knows everything is equal to 2n-4 for n>=4. - S. S. Wadhwa; PARAB 372 (gossip problem for n=5), Parabola, Proposal: 14(1978/1)28 Solution: 14(1978/3)31 by S. S. Wadhwa After the first day of classes, each of 5 different students knows a different bit of gossip about the teachers in their school. When they get to their separate homes, the telephoning begins. Assume that whenever anyone calls anyone else, each tells the other all the gossip he knows. What is the smallest number of calls after which it is possible for every student to know all 5 bits of gossip? Reviews: - Brenda Baker, Robert Shostak; Gossips and Telephones, Discrete Mathematics 2 (1972) 191-193 MR 46 # 68 From the authors' introduction: "The problem: There are $n$ ladies, and each of them knows some item of gossip not known to the others. They communicate by telephone, and whenever one lady calls another, they tell each other all that they know at that time. How many calls are required before each gossip knows everything? Answer: Let $f(n)$ be the minimum number of calls needed for $n$ people. It is easily shown that $f(1)=0$, $f(2)=1$, $f(3)=3$ and $f(4)=4cient according to the following procedure: one of four `chief' gossips first calls each of the remaining $n-4$ gossips, then the four learn each other's (and hence everyone's) information in 4 calls (as $f(4)=4$), and finally one of the four chiefs calls each of the other $n-4$ gossips. Theorem 1: $f(n)=2n-4$ for $n>4$." - Gerald Berman; The Gossip problem, Discrete Mathematics 4 (1973) 91 (Corrigendum p397) MR 46 # 7037 The author gives a simple (but, as pointed out in the corrigendum, incomplete) solution of the gossip problem of B. Baker and R. Shostack [Discrete Math. 2 (1972), no. 3, 191--193; MR 46 #68]. - Hajnal, A.; Milner, E. C.; Szemerédi, E. ; A cure for the telephone disease. Canad. Math. Bull. 15 (1972), 447--450. MR 47 #3184 Consider the following situation: There are $n$ people, each knowing an item of information not known to any of the others. They communicate by telephone and whenever two people talk to one another during a call, each informs the other of all the information known at the time. The problem is to determine the minimum number $f(n)$ of calls needed for everyone to know all the information. In this note the authors elegantly prove the surprisingly stubborn result that $f(n)=2n-4$ for $n\geq 4$. A proof along somewhat different lines has been given by B. Baker and R. Shostak [Discrete Math. 2 (1972), no. 3, 191--193; MR 46 #68]. Reviewed by R. L. Graham - J.-C. Bermond; Le problème des "ouvroirs". (French. English summary) Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 31--34, Colloq. Internat. CNRS, 260, CNRS, Paris, 1978. MR 81c:05056 This paper contains one of two recent short proofs of the "conference call" generalization of the gossip problem formulated and originally solved by K. Lebensold [Stud. Appl. Math. 52 (1973), 345--358; MR 49 #4797]. The method is based on that of A. Hajnal, E. C. Milner and E. Szemeredi [Canad. Math. Bull. 15 (1972), 447--450; MR 47 #3184] and thus gives detailed information about the set of elements which "know everything" after $m$ calls. An independent proof using different methods has also been given by D. J. Kleitman and J. B. Shearer [Discrete Math. 30 (1980), no. 2, 151--156; MR 81d:05068]. Reviewed by Richard T. Bumby - Richard T. Bumby; A problem with telephones, SIAM J. Alg. Disc. Meth. 2 (1981) 13-18 MR 82f:05083 The "telephone problem", also known as the "gossip problem", asks for the minimum number of calls required for $n$ people, for each to learn the others' information (gossip). The answer is $2n-4$. The author proves the "four-cycle conjecture": A graph whose edges are the calls of such a minimum set contains a four-cycle. Other properties of a minimum set of calls are obtained. D. J. Kleitman and J. B. Shearer [Discrete Math. 30 (1980), no. 2, 151--156; MR 81d:05068] Most of the four-cycle conjecture, based on the author's proof, and other related results. Reviewed by J. R. Griggs - D. J. Kleitman, J. B. Shearer; Further Gossip Problems, Discrete Mathematics 30 (1980) 151-156 MR 81d:05068 Starting from work of the reviewer ["A problem with telephones", SIAM J. Algebraic Discrete Methods, to appear] on the "gossip problem" and "4-cycle conjecture", the authors give additional properties which may be required of a 4-cycle in the graph of $2n-4$ calls pooling the information of $n$ people. A brief proof of the strengthened theorem is then given. In addition, similar methods are used to simplify a result of K. Lebensold [Studies in Appl. Math. 52 (1973), 345--358; MR 49 #4797] on conference calls. The result is also simplified by giving a more natural formula for the minimum number of calls. The proof is quite different from that recently published by J.-C. Bermond [Problemes combinatoires et theorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 31--34, CNRS, Paris, 1978]. Reviewed by Richard T. Bumby - Kenneth Lebensold; Efficient communication by phone calls, Studies in Appl. Math. 52 (1973) 345-358 MR 49 #4797 Let $f(n,k)$ denote the number of phone calls needed for $n$ persons to pool all their information in a succession of $k$-person party line phone calls. The author proves that $f(n,k)=[(n-2)/(k-1)]+[(n-1)/k]+1$ if $1\leq n\leq k\sp 2$ and $f(n,k)=2[(n-2)/(k-1)]$ for $n>k\sp 2$. Reviewed by M. S. Cheema - Tijdeman, R. ; On a telephone problem. Nieuw Arch. Wisk. (3) 19 (1971), 188--192. MR 49 #7151 A set of $n$ people, each initially possessing a unique item of information, make a sequence of telephone calls. During a call, the two parties tell one another the total amount of information known at the time. How many calls are necessary for everyone to know everything? This is the problem solved by the author, the answer being $2n-4$ when $n\geq 4$ and $0,1,3$ for $n=1,2,3$, respectively. The question is attributed to A. Boyd although, to the best of the reviewer's knowledge, it was first formulated by R. Chesters and S. Silverman (Univ. of Witwatersrand, unpublished, 1970). Previous solutions have been given by A. Hajnal, E. C. Milner and E. Szemeredi [Canad. Math. Bull. 15 (1972), 447--450; MR 47 #3184], B. Baker and R. Shostak [Dissertationes Math. 2 (1972), no. 3, 191--193; MR 46 #68], R. Bumby (unpublished) and J. H. Spencer (unpublished). Reviewed by R. L. Graham - Kn\"odel, Walter New gossips and telephones. Discrete Math. 13 (1975), no. 1, 95. MR 51 #15169 Consider $n$ persons, each of whom wants to telephone his one bit of information to all the others by means of a sequence of binary messages each of which has a fixed transmission time. The problem is to find how much time is required before ea ..... B. Baker and R. Shostak [Discrete Math. 2 (1972), no. 3, 191--193; MR 46 #68] showed that $2n-4$ calls are sufficient for $n>4$. In this short note the author establishes by a simple combinatorial argument that the optimal lower bounds are $\lceil\log\sb 2n\rceil$ for even $n$ and $\lceil\log\sb 2n\rceil+1$ for odd $n$. Reviewed by H. P. Edmundson - Cot, Norbert Extensions of the telephone problem. Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), pp. 239--256. Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976. MR 55 #2375 The telephone problem, known as the "gossip problem", first suggested by Erdos is considered. Solutions to the original problem were given by B. Baker and R. Shoshtak [Discrete Math. 2 (1972), 191--193; MR 46 #68] and some properties of the optimal solutions are discussed in this paper. Four possible extensions of the classical problem are then proposed; they are related to the following considerations: (a) the connections between the elements (i.e., gossips), (b) the ways these elements communicate, (c) the information they exchange, and (d) the quantities or functions to be minimized. The connections between the elements in the initial problem form a complete and undirected graph. In general, the graph which represents the connections is directed and not complete or undirected and not complete. A conjecture of Golumbic dealing with undirected graphs without 4-cycles is considered and the author proves it for a subclass of such graphs. Reviewed by M. M. Syslo - Krumme, David W.(1-TUFT-C) Reordered gossip schemes. (English. English summary) Discrete Math. 156 (1996), no. 1-3, 113--140. 97i:68154 Gossiping is a communication task in which each node of a graph has a piece of information which has to reach all other nodes. Communication is done by performing telephone calls along the edges of the graph. Every node can participate in at most one call at a time and during a call participating nodes exchange all previously accumulated information. The author proves a structural theorem concerning schemes of calls that achieve gossiping. The theorem says that calls of every such scheme can be rearranged into a sequence such that at most two calls cause each node to become fully informed and that the reverse sequence has the same property. This rather technical result has many important consequences. The author obtains well-known and important results from the theory of gossiping as easy corollaries of his theorem. For example he obtains a theorem stating that the smallest number of calls for gossiping in a complete $n$-node graph is $2n-4$ [cf. R. T. Bumby, SIAM J. Algebraic Discrete Methods 2 (1981), no. 1, 13--18; MR 82f:05083]. As such, the structural theorem adds a unifyi important application of the theorem is the solution of an open problem stated by N. Cot and unsolved for 20 years [cf. in Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), 239--256, Congressus Numerantium, XVII, Utilitas Math., Winnipeg, Man., 1976; MR 55 #2375]. It concerns the following generalization of the problem of finding a gossiping scheme with a minimum number of calls. Suppose that every edge of a graph is given a positive number representing the cost of calling along this edge. What is the minimum cost of a gossiping scheme (i.e., the minimum sum of costs of all calls)? It has been conjectured by O. Wolfson and A. Segall [SIAM J. Comput. 20 (1991), no. 3, 423--450; MR 91k:68037] that finding this minimum cost is NP-hard. Using his theorem the author gives a polynomial algorithm to find a minimum cost gossiping. More precisely, his algorithm works in time $O(n\sp 2m)$, where $n$ is the number of nodes and $m$ is the number of edges. Reviewed by Andrzej Pelc - G\"obel, F.(NL-TWEN-A); Cerdeira, J. Orestes; Veldman, H. J.(NL-TWEN-A) Label-connected graphs and the gossip problem. Discrete Math. 87 (1991), no. 1, 29--40. MR 92a:05074 The gossip problem is to determine the minimum number of telephone calls which must be made among $n$ persons so that each person can obtain the information known by all the other persons, assuming that when a call is made, the two persons share all the information available to them. This minimum number is known to be $2n-4$ [see, e.g., R. T. Bumby, SIAM J. Algebraic Discrete Methods 2 (1981), no. 1, 13--18; MR 82f:05083]. In the present paper the authors define a graph $G$ to be label-connected if it is possible to assign to each edge of $G$ a real number in such a way that for any two vertices $u$, $v$ of $G$, there exists a path from $u$ to $v$ along which the edge labels are in ascending order. Thus if the edge labels correspond to the time of the telephone calls, finding the minimum number of edges in a label-connected graph on $n$ vertices is equivalent to solving the gossip problem. The authors observe that if $\varphi(G)\leq 1$, then $G$ is label-connected, and that if $G$ is label-connected, then $\varphi(G)\leq 2$, where $\varphi(G)$ is the number of edges which must be added to $G$ to form two disjoint spanning trees. While each of these conditions can be checked in polynomial time, the authors show that when $\varphi(G)=2$, determining whether or not $G$ is label-connected is NP-complete. In the special case when $G$ has $n$ vertices and $2n-4$ edges, the authors show that $G$ is label-connected if and only if $G$ is a $C\sb 4$-graph, that is, $G=S\sb 1\cup S\sb 2$, where $S\sb 1$ and $S\sb 2$ are two edge-disjoint spanning forests each having two components, and $G$ has a four-cycle $uvwxu$ with edges $uv$, $wx$ in distinct components of $S\sb BæBVFvW2GgrBÂs of $S\sb 2$, thus affirming the 4-cycle conjecture of F. Harary and A. J. Schwenk [J. Franklin Inst. 297 (1974), 491--495; MR 50 #1980] about the gossip problem. Reviewed by Anthony E. Barkauskas - Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro; SFB 343 Preprints 94-116, University of Bielefeld Fast Gossiping by Short Messages To appear in: SIAM J. Comput. -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/