Enumerating the total number of subtrees of trees

MaRDI QIDQ6233677zbMATH OpenFDO

Authors Shuchao Li, Shujing Wang

Publication date 13 June 2012

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: Over some types of trees with a given number of vertices, which trees minimize or maximize the total number of subtrees or leaf containing subtrees are studied. Here are some of the main results: (1), Sharp upper bound on the total number of subtrees (resp. leaf containing subtrees) among $n$-vertex trees with a given matching number is determined; as a consequence, the $n$-vertex tree with domination number $gamma$ maximizing the total number of subtrees (resp. leaf containing subtrees) is characterized. (2), Sharp lower bound on the total number of leaf containing subtrees among $n$-vertex trees with maximum degree at least $Delta$ is determined; as a consequence the $n$-vertex tree with maximum degree at least $Delta$ having a perfect matching minimizing the total number of subtrees (resp. leaf containing subtrees) is characterized. (3), Sharp upper (resp. lower) bound on the total number of leaf containing subtrees among the set of all $n$-vertex trees with $k$ leaves (resp. the set of all $n$-vertex trees of diameter $d$) is determined.

This page was built for publication: Enumerating the total number of subtrees of trees

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