Telephone problems with failures. (English) Zbl 0578.05059

Summary: Consider a multigraph \(G\) on \(n\) vertices whose edges are linearly ordered. The vertices of \(G\) may represent people and the edges two-way communication between pairs of people. A vertex \(v\) is \(k\)-failure-safe in communicating with a vertex \(w\) if there is a path of ascending edges from \(v\) to \(w\) even when any \(k\)-edges of \(G\) are deleted. In this paper, we show that the minimum size \(\mu (n,k)\) of \(G\) such that one vertex communicates \(k\)-failure-safe with every other vertex is given by \(\mu (n,k)=\lceil ((k+2)/2)(n-1)\rceil\) for \(k\leq n-2\) and \(\mu (n,k)=\lceil ((k+1)/2n\rceil\) for \(k\geq n-2\). We also show that for \(k\geq 1\) the minimum size \(\tau (n,k)\) of \(G\) such that every vertex communicates \(k\)-failure-safe with every other vertex satisfies \(\mu (n,k)+n-2\lceil \sqrt{n}\rceil \leq \tau (n,k)\leq \lfloor (k+3/2)(n-1)\rfloor.\) The problem of finding \(\tau(n,k)\) for \(k=0\) is the well-known telephone problem.


05C35 Extremal problems in graph theory
90B10 Deterministic network models in operations research
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] Baker, B.; Shostah, R., Gossips and telephones, Discrete Math., 2, 191, (1972) · Zbl 0245.05002
[2] Bumby, RichardT., A problem with telephones, SIAM J. Algebraic Discrete Methods, 2, 13, (1981) · Zbl 0499.05034
[3] Hajnal, A.; Milner, E. C.; Szemeredi, E., A cure for the telephone disease, Canad. Math. Bull., 15, 447, (1972) · Zbl 0251.05132
[4] Harary, Frank; Schwenk, AllenJ., The communication problem on graphs and digraphs, J. Franklin Inst., 297, 491, (1974) · Zbl 0307.05118
[5] Kleitman, D. J.; Shearer, J. B., Further gossip problems, Discrete Math., 30, 151, (1980) · Zbl 0444.05015
[6] Tijdeman, R., On a telephone problem, Nieuw Arch. Wisk. (3), 19, 188, (1971) · Zbl 0226.05001
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.