Two Broadcasting Problems in FaultyHypercubes

We consider two broadcasting problems in the n-dimensional hypercube under the shouting communication mode, i.e. any node of a network can inform all its neighbours in one time step. In addition, during any time step a number of links of the network can be faulty. Moreover the faults are dynamic. The first problem is to find an upper bound on the number of time steps necessary to complete the broadcasting if at most n - 1 links are faulty in any step. Fraigniaud and Peyrat [10] proved that n+O(log n) time steps are sufficient. De Marco and Vaccaro [8] decreased the upper bound to n + 7 and showed a worst case lower bound n + 2 for n ≥ 3. We prove that n + 2 time steps are sufficient. The second problem from [8] is to find the maximal number k such that the broadcasting time remains n if at most k faults are allowed in any step. We prove that k equals either n-2 or n-3. Our method is related to the isoperimetric problem in graphs and can be applied to other networks.