zbMATH — the first resource for mathematics

Multiple isolation of nodes in recursive trees. (English) Zbl 1300.05285
Summary: We introduce the problem of isolating several nodes in random recursive trees by successively removing random edges, and study the number of random cuts that are necessary for the isolation. In particular, we analyze the number of random cuts required to isolate $$\ell$$ selected nodes in a size-$$n$$ random recursive tree for three different selection rules, namely (i) isolating all of the nodes labelled $$1,2\ldots,\ell$$ (thus nodes located close to the root of the tree), (ii) isolating all of the nodes labelled $$n+1-\ell,n+2-\ell,\ldots n$$ (thus nodes located at the fringe of the tree), and (iii) isolating $$\ell$$ nodes in the tree, which are selected at random before starting the edge-removal procedure. Using a generating functions approach we determine for these selection rules the limiting distribution behaviour of the number of cuts to isolate all selected nodes, for $$\ell$$ fixed and $$n \to \infty$$.

MSC:
 05C80 Random graphs (graph-theoretic aspects) 05C05 Trees 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 60F05 Central limit and other weak theorems
Full Text: