The \(k\)-cut model in deterministic and random trees (Q2223481)

This paper studies a \(k\)-cut cutting down process over conditioned Galton-Watson trees. The process generally starts with a tree \(T_n\) over \(n\) nodes by choosing uniformly at random a node from the component containing the root and cutting the chosen node once. If the vertex has been cut \(k\) times, it will be removed from the graph. The process continues until the root has been removed. The total number of cuts needed to end the procedure is called the \(k\)-cut number denoted by \(K_k(T_n)\). If \(T_n\) is a Galton-Watson tree conditioned on its number of vertices being \(n\) with offspring distribution defined with unit expectation and finite variance \(\sigma^2\), then it is shown that \(\sigma^{-1/k}n^{-1+1/2k}K(T_n)\) converges in distribution to \(Z_{CRT}\) as \(n\) goes to infinity, where \(Z_{CRT}\) is a non-degenerate variable with the distribution determined by all its moments, which have been worked out.