When considering the total number of subtrees of trees, the extremal structures which maximize this number among binary trees and trees with a given maximum degree lead to some interesting facts that correlate to some other graphical indices in applications. Along this line, it is interesting to study that over some types of trees with a given order, which trees minimize or maximize this number. Here are our main results: (1) The extremal tree which minimizes the total number of subtrees among $n$-vertex trees with $k$ pendants is characterized. (2) The extremal tree which maximizes (resp. minimizes) the total number of subtrees among $n$-vertex trees with a given bipartition is characterized. (3) The extremal tree which minimizes the total number of subtrees among the set of all $q$-ary trees with $n$ non-leaf vertices is identified. (4) The extremal $n$-vertex tree with given domination number maximizing the total number of subtrees is characterized.
@article{10_37236_2186,
author = {Shuchao Li and Shujing Wang},
title = {Further analysis on the total number of subtrees of trees},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {4},
doi = {10.37236/2186},
zbl = {1266.05010},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2186/}
}
TY - JOUR
AU - Shuchao Li
AU - Shujing Wang
TI - Further analysis on the total number of subtrees of trees
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/2186/
DO - 10.37236/2186
ID - 10_37236_2186
ER -
%0 Journal Article
%A Shuchao Li
%A Shujing Wang
%T Further analysis on the total number of subtrees of trees
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2186/
%R 10.37236/2186
%F 10_37236_2186
Shuchao Li; Shujing Wang. Further analysis on the total number of subtrees of trees. The electronic journal of combinatorics, Tome 19 (2012) no. 4. doi: 10.37236/2186
