Telephone Problems with Failures

Abstract

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 $\upsilon $ is k-failure-safe in communicating with a vertex w if there is a path of ascending edges from $\upsilon $ 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\leqq n - 2$ and $\mu ( n,k ) = \lceil ( ( k + 1 )/2 )n \rceil $ for $k\geqq n - 2$. We also show that for $k\geqq 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 \leqq \tau ( n,k )\leqq \lfloor ( k + 3/ 2 ) ( n - 1 ) \rfloor $. The problem of finding $\tau ( n,k )$ for $k = 0$ is the well-known telephone problem.