Distinct Fringe Subtrees in Random Trees

DOI10.1007/S00453-022-01013-YMaRDI QIDQ6367250arXivFDO

Authors Louisa Seelbach Benkner, Stephan Wagner

Publication date 10 May 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00453-022-01013-Y

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

arXiv classification

math.COcs.DM

Abstract: A fringe subtree of a rooted tree is a subtree induced by one of the vertices and all its descendants. We consider the problem of estimating the number of distinct fringe subtrees in two types of random trees: simply generated trees and families of increasing trees (recursive trees, $d$-ary increasing trees and generalized plane-oriented recursive trees). We prove that the order of magnitude of the number of distinct fringe subtrees (under rather mild assumptions on what `distinct' means) in random trees with $n$ vertices is $n/sqrtlogn$ for simply generated trees and $n/logn$ for increasing trees.

This page was built for publication: Distinct Fringe Subtrees in Random Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367250)