The proportion of trees that are linear

DOI10.1016/J.DISC.2020.112008MaRDI QIDQ785803zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

caterpillarslinear trees

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Enumeration in graph theory (05C30)

Abstract: We study several enumeration problems connected to linear trees, a broad class which includes stars, paths, generalized stars, and caterpillars. We provide generating functions for counting the number of linear trees on $n$ vertices, characterize the asymptotic growth rate of the number of nonisomorphic linear trees, and show that the distribution of $k$-linear trees on $n$ vertices follows a central limit theorem.

Recommendations

• Corrigendum to: ``The proportion of trees that are linear
• Linear MIM-width of trees
• Tree topologies along a tropical line segment
• On optimal linear arrangements of trees
• On the width of an orientation of a tree
• Linearity criterion for the selection of an optimal tree
• scientific article; zbMATH DE number 798854
• Analogical Proportions and Binary Trees
• The geometry of plane linear trees
• A distance approximating trees

Cites work

• Analytic combinatorics
• Eigenvalues, multiplicities and graphs
• Ordered multiplicity lists for eigenvalues of symmetric matrices whose graph is a linear tree
• The number of caterpillars

Cited in

(8)

• The enumeration of trees with and without given limbs
• The inverse eigenvalue problem for linear trees
• Corrigendum to: ``The proportion of trees that are linear
• Paths vs. stars in the local profile of trees
• Counting christmas trees
• Multiplicity lists by diameter: all trees of diameter \(< 7\)
• Maximum linear arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs
• Using linear forms to determine the set of integers realizable by \((g_ 0,g_ 1,\dots ,g_ n)\)-trees

This page was built for publication: The proportion of trees that are linear

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