On the combinatorics of rooted binary phylogenetic trees (Q1430529)

This paper studies the subtree pruning and regrafting (SPR) operation on rooted phylogenetic trees: a subtree is pruned by deleting an edge and it is regrafted by inserting it into another edge. In unrooted trees the size of SPR-related neighborhood is dependent on the topology of the tree, and it was determined by \textit{B. Allen} and \textit{M. Steel} [Ann. Comb. 5, No. 1, 1--15 (2001; Zbl 0978.05023)]. However, in the rooted case this size independents upon the topology. This paper gives an efficient algorithm to determine this size. It gives also sharp bounds on this size, which in turn may allow to investigate the diameter of the tree-space.