Telephone problems with failures. (English) Zbl 0578.05059

Berman, Kenneth A.; Hawrylycz, Michael

SIAM J. Algebraic Discrete Methods 7, 13-17 (1986).

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.

MSC:

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

Keywords:

communication network; multigraph; communication; k-failure-safe

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