Fragmentation of Random Trees
Z. Kalay and E. Ben-Naim
We study fragmentation of a random recursive tree into a forest by
repeated removal of nodes. The initial tree consists of $N$ nodes
and it is generated by sequential addition of nodes with each new
node attaching to a randomly-selected existing node. As nodes are
removed from the tree, one at a time, the tree dissolves into an
ensemble of separate trees, namely, a forest. We study statistical
properties of trees and nodes in this heterogeneous forest, and find
that the fraction of remaining nodes $m$ characterizes the system in
the limit $N\to \infty$. We obtain analytically the size density
$\phi_s$ of trees of size $s$. The size density has power-law tail
$\phi_s\sim s^{-\alpha}$ with exponent
$\alpha=1+\tfrac{1}{m}$. Therefore, the tail becomes steeper as
further nodes are removed, and the fragmentation process is unusual
in that exponent $\alpha$ increases continuously with time. We also
extend our analysis to the case where nodes are added as well as
removed, and obtain the asymptotic size density for growing trees.
source,
pdf