K-cut on paths and some trees

Abstract

We define the (random) $k$-cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon except now a node must be cut $k$ times before it is destroyed. The first order terms of the expectation and variance of ${\mathcal{X}}_n$, the $k$-cut number of a path of length $n$, are proved. We also show that ${\mathcal{X}}_n$, after rescaling, converges in distribution to a limit ${\mathcal{B}}_k$, which has a complicated representation. The paper then briefly discusses the $k$-cut number of some trees and general graphs. We conclude by some analytic results which may be of interest.

arXiv commentThe paper was originally titled "Cutting resilient networks"

References in corpus (2)

• Cutting down trees with a Markov chainsaw
• Inversions in split trees and conditional Galton--Watson trees

Cited by in corpus (1)

• $k$-cut model for the Brownian Continuum Random Tree