Premium
Transversals in Trees
Author(s) -
Campos Victor,
Chvátal Vašek,
Devroye Luc,
Taslakian Perouz
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21655
Subject(s) - library science , computer science , operations research , engineering
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 oftransversals 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 leastone 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 atmost d children has aunique minimal element with respect to this partial order and we describethis tree. In addition, we determine asymptotically the expected values of c(T,k) in special families of trees. © 2012 Wiley Periodicals, Inc.SCOPUS: ar.jFLWINinfo:eu-repo/semantics/inPres