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

DOI10.1016/J.JMAA.2015.09.007MaRDI QIDQ890484zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(5)

• scientific article; zbMATH DE number 4187815 (Why is no real title available?)
• The number of rooted trees of given depth
• Counting embeddings of rooted trees into families of rooted trees
• scientific article; zbMATH DE number 6385357 (Why is no real title available?)
• Properties related to the function of the number of undirected non-isomorphic trees

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)