k-cut on paths and some trees

Xing Shi Cai, Cecilia Holmgren, Luc Devroye, F Skerman

Research output: Contribution to journalArticle (Academic Journal)

32 Downloads (Pure)

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 X_n, the k-cut number of a path of length n, are proved. We also show that X_n, after rescaling, converges in distribution to a limit 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.
Original languageEnglish
Article number53
Number of pages22
JournalElectronic Journal of Probability
Volume24
DOIs
Publication statusPublished - 5 Jun 2019

Keywords

  • cutting
  • k-cut
  • random trees

Fingerprint Dive into the research topics of 'k-cut on paths and some trees'. Together they form a unique fingerprint.

Cite this