The asymptotic number of non-isomorphic rooted trees obtained by rooting a tree

DOI10.1016/J.JMAA.2015.09.007zbMATH Open1325.05055arXiv1207.3915OpenAlexW1275724971MaRDI QIDQ890484FDOQ890484

Authors: Xueliang Li, Yongtang Shi, Yiyang Li 

Publication date: 10 November 2015

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Abstract: Let $mathcal{T}_n$ be the set of trees with $n$ vertices. Suppose that each tree in $mathcal{T}_n$ is equally likely. We show that the number of different rooted trees of a tree equals $(m{u}_r+o(1))n$ for almost every tree of $mathcal{T}_n$, where $m{u}_r$ is a constant. As an application, we show that the number of any given pattern in $mathcal{T}_n$ is also asymptotically normally distributed with mean $simm{u}_{M}n$ and variance $simsigm{a}_{M}n$, where $m{u}_M,sigm{a}_M$ are some constants related to the given pattern. This solves an open question claimed in Kok's thesis.

Full work available at URL: https://arxiv.org/abs/1207.3915

Recommendations

• The Distribution of Patterns in Random Trees
• The number of rooted trees of given depth
• Pattern distribution in various types of random trees
• On the number of nonisomorphic subtrees of a tree
• scientific article; zbMATH DE number 3849252

zbMATH Keywords

automorphismpatternlimiting distributionrooted treecounting, generating function

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• Random graphs.
• Title not available (Why is that?)
• The number of trees
• Isomorphism and symmetries in random phylogenetic trees
• The distribution of degrees in a large random tree
• Vertices of degree \(k\) in random unlabeled trees
• The distribution of nodes of given degree in random trees
• The Distribution of Patterns in Random Trees
• Nodes of large degree in random trees and forests
• Pattern distribution in various types of random trees
• The asymptotic value of the Randić index for trees
• The expected number of symmetries in locally restricted trees. II

Cited In (4)

• Properties related to the function of the number of undirected non-isomorphic trees
• Title not available (Why is that?)
• Counting embeddings of rooted trees into families of rooted trees
• Title not available (Why is that?)

This page was built for publication: The asymptotic number of non-isomorphic rooted trees obtained by rooting a tree

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