Telephone problems with failures.

*(English)*Zbl 0578.05059Summary: 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.

##### MSC:

05C35 | Extremal problems in graph theory |

90B10 | Deterministic network models in operations research |

94C15 | Applications of graph theory to circuits and networks |

PDF
BibTeX
XML
Cite

\textit{K. A. Berman} and \textit{M. Hawrylycz}, SIAM J. Algebraic Discrete Methods 7, 13--17 (1986; Zbl 0578.05059)

Full Text:
DOI

##### References:

[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.