Transversals in trees
From MaRDI portal
Publication:4920649
DOI10.1002/JGT.21655zbMATH Open1262.05023arXiv0705.1806OpenAlexW1901357871MaRDI QIDQ4920649FDOQ4920649
Authors:
Publication date: 21 May 2013
Published in: Journal of Graph Theory (Search for Journal in Brave)
Abstract: A transversal in a rooted tree is any set of nodes that meets every path from the root to a leaf. We let c(T,k) denote the number of transversals of size k in a rooted tree T. We define a partial order on the set of all rooted trees with n nodes by saying that a tree T succeeds a tree T' if c(T,k) is at least c(T',k) for all k and strictly greater than c(T',k) for at least one k. We prove that, for every choice of positive integers d and n, the set of all rooted trees on n nodes where each node has at most d children has a unique minimal element with respect to this partial order and we describe this tree.
Full work available at URL: https://arxiv.org/abs/0705.1806
Recommendations
Cites Work
- Probability Inequalities for Sums of Bounded Random Variables
- Probability Inequalities for the Sum of Independent Random Variables
- Trees with Hamiltonian square
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Branching processes in the analysis of the heights of trees
- On the Tchebychef Inequality of Bernstein
- Universal Limit Laws for Depths in Random Trees
Cited In (8)
- Trees with minimum number of infima closed sets
- On the number of transversals in random trees
- Transversal factors and spanning trees
- Polynomial invariants for rooted trees related to their random destruction
- Transitivity of trees
- A modification of the random cutting model
- Intransitive trees
- Title not available (Why is that?)
This page was built for publication: Transversals in trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4920649)
