Cutting resilient networks -- complete binary trees (Q2278120)

Summary: In our previous work, we introduced the random \(k\)-cut number for rooted graphs. In this paper, we show that the distribution of the \(k\)-cut number in complete binary trees of size \(n\), after rescaling, is asymptotically a periodic function of \(\lg n - \lg \lg n\). Thus there are different limit distributions for different subsequences, where these limits are similar to weakly \(1\)-stable distributions. This generalizes the result for the case \(k = 1\), i.e., the traditional cutting model, by \textit{S. Janson} [in: Mathematics and computer science III. Algorithms, trees, combinatorics and probabilities. Proceedings of the international colloquium of mathematics and computer sciences. Basel: Birkhäuser. 241--253 (2004; Zbl 1063.60018)].