The \(k\)-cut number of rooted graphs was introduced by Cai et al. as a generalization of the classical cutting model by Meir and Moon. In this paper, we show that all moments of the \(k\)-cut number of conditioned Galton-Watson trees converge after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson. Using the same method, we also show that the \(k\)-cut number of various random or deterministic trees of logarithmic height converges in probability to a constant after rescaling, such as random split-trees, uniform random recursive trees, and scale-free random trees.
@article{10_37236_9486,
author = {Gabriel Berzunza and Xing Shi Cai and Cecilia Holmgren},
title = {The \(k\)-cut model in deterministic and random trees},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/9486},
zbl = {1462.60010},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9486/}
}
TY - JOUR
AU - Gabriel Berzunza
AU - Xing Shi Cai
AU - Cecilia Holmgren
TI - The \(k\)-cut model in deterministic and random trees
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9486/
DO - 10.37236/9486
ID - 10_37236_9486
ER -
%0 Journal Article
%A Gabriel Berzunza
%A Xing Shi Cai
%A Cecilia Holmgren
%T The \(k\)-cut model in deterministic and random trees
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9486/
%R 10.37236/9486
%F 10_37236_9486
Gabriel Berzunza; Xing Shi Cai; Cecilia Holmgren. The \(k\)-cut model in deterministic and random trees. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9486
