Almost all trees have tribe number 2 or 3

DOI10.1016/0012-365X(93)E0013-TMaRDI QIDQ1897446zbMATH OpenOpenAlexWikidataFDO

Authors János Komlós, W. O. J. Moser

Publication date 27 August 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)e0013-t

zbMATH Keywords

foresttreetribe number

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Review text

For a fixed \(\varepsilon\leq 1/2\), the tribe number \(t_T(\varepsilon)\) of \(T\) is defined as the smallest integer \(r\), such that for every vertex \(v\) in \(T\), the forest obtained from deleting \(v\) from \(T\) contains a collection of at most \(r\) trees that contain together more than \((1- \varepsilon)n\) vertices (\(n\) denoting the number of vertices of \(T\)). The tribe number of a tree can be arbitrarily large. However, as is shown in this paper, almost every tree has tribe number 2 or 3 (with respect to any fixed \(\varepsilon\leq 1/2\)).

Recommendations

• Almost all trees have an even number of independent sets
• On Major and Minor Branches of Rooted Trees
• Sub-trees of a random tree
• scientific article; zbMATH DE number 568825
• Random Trees in Random Graphs

This page was built for publication: Almost all trees have tribe number 2 or 3

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