<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Bounds on the Size of the TBR Unit-Neighbourhood
Peter J. Humphries
Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch 8140, New Zealand
Annals of Combinatorics 14 (4) pp.479-485 December, 2010
AMS Subject Classification: 05C05; 92D15
In this paper, we study the unit-neighbourhood of the tree bisection and reconnection operation on unrooted binary phylogenetic trees. Specifically, we provide a recursive method to calculate the size of the unit-neighbourhood for any tree in the space Jn of unrooted binary phylogenetic trees with n-leaves. We also give both upper and lower bounds on this size for all trees in Jn, and
characterize those trees for which the stated upper bound is sharp.
Keywords: tree bisection and reconnection, unit-neighbourhood, unrooted trees


1. Allen, B.L., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Combin. 5(1), 1--15 (2001)

2. Hein, J.: A heuristic method to reconstruct the history of sequences subject to recombination. J. Mol. Evol. 36(4), 369--405 (1993)

3. Maddison, D.R.: The discovery and importance of multiple islands of most-parsimonious trees. Syst. Zool. 40(3), 315--328 (1991)

4. Robinson, D.F.: Comparison of labeled trees with valency three. J. Combin. Theory Ser. B 11(2), 105--119 (1971)

5. Song, Y.S.: On the combinatorics of rooted binary phylogenetic trees. Ann. Combin. 7(3), 365--379 (2003)