Regensburg 2016 – wissenschaftliches Programm
DY 30.8: Poster
Dienstag, 8. März 2016, 18:15–21:00, Poster C
Leaf-to-leaf distances in ordered Catalan tree graphs — Andrew M. Goldsborough, John M. Fellows, Matthew Bates, S. Alex Rautu, George Rowlands, and •Rudolf A. Römer — University of Warwick, Coventry, CV4 7AL, UK
We study the average leaf-to-leaf path lengths on ordered Catalan tree graphs with n nodes and show that these are equivalent to the average length of paths starting from the root node. We give an explicit analytic formula for the average leaf-to-leaf path length as a function of separation of the leaves and study its asymptotic properties. At the heart of our method is a strategy based on an abstract graph representation of generating functions which we hope can be useful also in other contexts.