% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P48}{19(4)}{2012}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts,url}
\usepackage{mathrsfs, amscd,amssymb,amsthm,amsmath,bm,graphicx,psfrag,subfigure}
% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
%\newenvironment{kst}
%{\setlength{\leftmargini}{2\parindent}
% \begin{itemize}
% \setlength{\itemsep}{-1.1mm}}
%{\end{itemize}}

%\newenvironment{lst}
%{\setlength{\leftmargini}{0.85\parindent}
% \begin{itemize}
% \setlength{\itemsep}{-1.1mm}}
%{\end{itemize}}
%
%\newenvironment{wst}
%{\setlength{\leftmargini}{1.5\parindent}
% \begin{itemize}
% \setlength{\itemsep}{-1.1mm}}
%{\end{itemize}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins
\sloppy


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Further analysis on the total number\\ of subtrees of trees}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Shuchao Li$^{1,}$\thanks{Financially supported by
the National Natural Science Foundation of China (Grant Nos. 11071096, 11271149) and the Special Fund for Basic Scientific Research of Central Colleges (CCNU11A02015).}\ \ and\ \  Shujing Wang$^2$\\
\small Faculty of Mathematics and Statistics\\[-0.8ex]
\small Central China Normal
University\\[-0.8ex]
\small Wuhan 430079, P.R. China\\
\small\tt $^1$lscmath@mail.ccnu.edu.cn,  $^2$wang06021@126.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Mar 29, 2012}{Dec 5, 2012}{Dec 31, 2012}\\
\small Mathematics Subject Classifications: 05C05, 05C07, 05C35,}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  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.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} subtrees; Wiener index;
leaves; bipartition; $q$-ary tree; domination number
\end{abstract}

\section{Introduction}

We consider only connected simple graphs (i.e., finite, undirected graphs without loops or multiple edges). We
follow the notations and terminology in \cite{B-M-G} except otherwise stated.

Let $G=(V_G, E_G)$ be a graph with $u,v\in V_G$, $d_G(u)$ (or $d(u)$ for short) denotes the
degree of $u$. Throughout we denote by $P_n,\, K_{1,n-1}$ the path and
star on $n$ vertices, respectively. $G-v,\, G-uv$ denote
the graph obtained from $G$ by deleting vertex $v \in V_G$, or edge
$uv \in E_G$, respectively (this notation is naturally extended if
more than one vertex or edge is deleted). Similarly,
$G+uv$ is obtained from $G$ by adding edge $uv \not\in E_G$. For $v\in V_G,$ let
$N_G(v)$ (or $N(v)$ for short) denote the set of all the adjacent vertices of $v$ in $G.$
We refer to vertices of degree 1 of $G$ as \textit{leaves}
(or \textit{pendant vertices}), and the edges incident to leaves are called \textit{pendant edges}. Let $PV(G)$ denote the set of all leaves of $G$. For convenience, let $\mathscr{T}_n^k$ be the set of all $n$-vertex trees with $k$ leaves.

Let $G$ be a connected bipartite graph with $n$ vertices. Hence its vertex set can be partitioned into
two subsets $V_1$ and $V_2$, such that each edge joins a vertex in $V_1$ with a vertex in $V_2$. Suppose that $V_1$ has
$p$ vertices and $V_2$ has $q$ vertices, where $p+q = n$. Then we say that $G$ has a $(p, q)$-\textit{bipartition} $(p \leqslant q)$. For convenience, let $\mathscr{P}_n^{p, q}$ be the set of all $n$-vertex trees, each of which has a $(p, q)$-bipartition. Given positive integers $n, q$ with $q\ge 2$, we call $T$ a \textit{complete $q$-ary tree} (or \textit{$q$-ary tree} for short) if any
non-pendant vertex $v$ in $T$ has exactly $q$ neighbours. Denote by $\mathscr{A}_n^q$ the class of $q$-ary trees with $n$ non-leaf
vertices ($(q-2)n+2$ leaves).

A subset $S$ of $V_G$ is called a \textit{dominating set} of $G$ if
 for every vertex $v\in V_G\setminus S$, there exists a vertex $u\in S$ such that
$v$ is adjacent to $u$.  For a dominating set $S$ of graph $G$
with $v\in S$, $u\in V_G\setminus S$, if $vu\in E_G$, then $u$ is said to
be dominated by $v$. The \textit{domination number} of $G$, denoted
by $\gamma(G)$, is defined as the minimum cardinality of dominating
sets of $G$. Denote by $\mathscr{D}_n^\gamma$ the set of all $n$-vertex trees with domination number $\gamma$.

Given a tree $T$, a \textit{subtree} of $T$ is just a connected induced subgraph of $T$. The number of subtrees $F(T)$
has received much attention. Let $T$ denote a tree with $n$ vertices each of whose non-leaves has degree at least three, Andrew and Wang \cite{17} showed that the average orders in the subtrees of $T$ is at least $\frac{n}{2}$ and strictly less than $\frac{3n}{4}$. Sz\'ekely and Wang \cite{20} characterized the binary trees with $n$ leaves that have the greatest number of subtrees. Kirk and Wang \cite{19} identified the tree, for a given size and such that the vertex degree is bounded, having the greatest number of subtrees.  Sz\'ekely and Wang \cite{21} gave a formula for the maximal number of subtrees a binary tree can possess over a given number of vertices.  They also show that caterpillar trees (trees containing a path such that each vertex not belonging to the path is adjacent to a vertex on the path) have the smallest number of subtrees among binary trees. Yan and Ye \cite{25} characterized the tree with the diameter at least $d$ having the maximum number of subtrees.

In 2012, Zhang, Zhang, Gray, and Wang \cite{28,29} determined the extremal tree with given degree sequence having the largest number of subtrees. As a consequence, they obtained the extremal trees with maximum number of subtrees among the set of trees with given number of independence number, leaves, matching number, respectively. Zhang and Zhang \cite{270} investigated the structures of an extremal tree which has the minimal
number of subtrees in the set of all trees with a very special degree sequence. For some related results on the enumeration of subtrees of trees, one may also see Sz\'{e}kely and Wang \cite{02,03}, Wang \cite{12} and Song \cite{S-C-W}.

An interesting fact that among the $n$-vertex trees of given degree sequence, the extremal one that maximizes the total number of subtrees is exactly the one that minimizes some chemical indices such as the well known Wiener index, and vice versa; see [13, 19-23]. The correlation between these and other indices has been the subject of investigation in the recent work of Sz\'ekley, Wang and Wu \cite{S-W-W}; see also the work of Wagner \cite{W-W-W}. Along this line, it is interesting and nature to study the extremal problems on $F(T)$ in some other types of trees. In particular, it is interesting to characterize the extremal trees with minimal number of subtrees among some types of trees. Motivated by these facts, in this paper we focus on characterizing the structure of trees maximizing/minimizing $F(T)$ among $\mathscr{T}_n^k, \mathscr{P}_n^{p,q}, \mathscr{A}_n^q$ and $\mathscr{D}_n^\gamma$, respectively.

Let $P_k(a,b)$ be a tree obtained by attaching $a$ and $b$ pendant vertices to the two pendant vertices of $P_k$, respectively. In particular, if $k=1$, then $P_k(a,b)=K_{1,a+b}$. It is straightforward to check that $P_{n-k}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil) \in \mathscr{T}_n^k$. It is known that the Wiener index among $n$-vertex trees with $k$ pendant vertices is maximized by $P_{n-k}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil)$; see Dobrynin, Entringer and Gutman \cite{15}.
We are to show the counterpart of this result for the number of subtrees.
\begin{theorem}
Precisely the graph $P_{n-k}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil)$ minimizes the total number of subtrees among ${\mathscr T}_n^k.$
\end{theorem}


Consider a star $K_{1,p}$ with $p + 1$ vertices and attach $q-1$ pendant edges to a non-central vertex of the
star $K_{1,p}$. The resulting tree with $p + q$ vertices has a $(p, q)$-bipartition. Denote the resulting tree by
$D(p, q)$; see Fig. 1. Obviously, $D(p, q)\in \mathscr{P}_n^{p,q}$. We call $D(p, q)$ a \textit{double star}. Ye and Chen \cite{Y-L-Z}
characterized the tree with given bipartition having minimal energy and Hosoya index. Then it is natural to consider the extremal problem on the total number of subtrees of trees with given bipartition.
\begin{figure}[h!]
\begin{center}
  % Requires \usepackage{graphicx}
\psfrag{a}{$p-1$}\psfrag{b}{$q-1$}\psfrag{c}{$p-2$}\psfrag{d}{$q-1$}\psfrag{e}{$q-2$}
\psfrag{A}{$D(p, q)$}\psfrag{B}{$B(p,q)$}\psfrag{C}{$B(2,q)$}%\psfrag{u}{$u$}\psfrag{v}{$v$}\psfrag{t}{$q-2$}
  \includegraphics[width=40mm]{fig1.eps}\\
  \caption{Tree $D(p, q).$ }
\end{center}
\end{figure}
\begin{theorem}
Precisely the graph $D(p, q)$ (resp. $P_{2p-1}(\lfloor\frac{n-2p+1}{2}\rfloor,\lceil\frac{n-2p+1}{2}\rceil)$) maximizes (resp. minimizes) the total number of subtrees among $\mathscr{P}_n^{p,q}.$
\end{theorem}

Consider the path $P_{n+2}$ and attach $q-2$ pendant edges to each of the
non-leaf vertices of $P_{n+2}$. Denote the resulting tree by $\hat{T}_n^q$ (see Fig. 2).
It is easy to see that $\hat{T}_n^q \in \mathscr{A}_n^q$. In view of Theorem 2.3 in \cite{19}, it is easy to determine the tree in
$\mathscr{A}_n^q$ which maximizes the total number of subtrees. It is natural and interesting to characterize the tree with minimum number of subtrees of trees among $\mathscr{A}_n^q.$
\begin{figure}[h!]
\begin{center}
  % Requires \usepackage{graphicx}
\psfrag{i}{$v_i$}\psfrag{n}{$v_n$}\psfrag{a}{$v_{i-1}$}\psfrag{b}{$v_{i+1}$}
\psfrag{c}{$v_{n+1}$}\psfrag{d}{$q-2$}\psfrag{0}{$v_0$}\psfrag{1}{$v_1$}
\psfrag{1}{$v_1$}\psfrag{2}{$v_2$}\psfrag{A}{$\hat{T}_n^q$}\psfrag{B}{$T_{n,k}$}
\psfrag{3}{$v_{i-1}$}\psfrag{4}{$v_i$}\psfrag{5}{$v_{i+1}$}\psfrag{6}{$v_{n-k+1}$}\psfrag{k}{$k-1$}
  \includegraphics[width=80mm]{fig2.eps}\\
  \caption{Tree $\hat{T}_n^q.$ }
\end{center}
\end{figure}
\begin{theorem}
Precisely the graph $\hat{T}_n^q$ (see Fig. 2) minimizes the total number of subtrees among $\mathscr{A}_n^q.$
\end{theorem}

Let $A(n,\gamma)$ be the tree that is obtained by attaching $\gamma-1$ pendant edges to $\gamma-1$ pendant vertices of the star $K_{1, n-\gamma}$. It is routine to check that $A(n,\gamma)\in \mathscr{D}_n^\gamma$. He, Wu and Yu \cite{H-C-X} characterized the tree with given domination number having minimal energy. It is natural to consider the extremal problem on the total number of subtrees of trees with given bipartition.
\begin{theorem}
Precisely the graph $A(n,\gamma)$ maximizes the total number of subtrees in $\mathscr{D}_n^\gamma.$
\end{theorem}
\begin{theorem}
Precisely the graph $P_{\frac{n}{2}}\circ K_1$ minimizes the total number of subtrees in $\mathscr{D}_n^\frac{n}{2},$ where $P_{\frac{n}{2}}\circ K_1$ is obtained by attaching a leaf to each vertex of the path $P_{\frac{n}{2}}$.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Some Lemmas}

In this section, we give some necessary results which will be used to prove our main results.
For a set $S,$ let $|S|$ denote its cardinality. For two graphs $G_1, G_2$, if $G_1$ is a \textit{connected subgraph} of $G_2$, then we denote it by $G_1\subseteq G_2$.
Given a tree $T$ with $u,\,v\in V_T$, let
$$
\begin{array}{ll}
  \ \ \  f_T(u)  =  |\{T':\ \ T'\subseteq T, \, u\in V_{T'}\}|, & f_T(u*v) =  |\{T':\ \ T'\subseteq T, \, u,\,v\in V_{T'}\}|,\\
  f_T(u/v) =  |\{T':\ \ T'\subseteq T, \, u\in V_{T'}, v\not\in V_{T'}\}|, &\ \ \ \ \  F(T)=|\{T': \, T'\subseteq T,\, |V_{T'}|\geqslant 1\}|.
\end{array}
$$
Then one has
\begin{equation}\label{2.1}
    f_T(u)=f_T(u*v)+f_T(u/v), \ \ \ f_T(v)=f_T(u*v)+f_T(v/u).
\end{equation}
\begin{figure}[h!]
\begin{center}
  % Requires \usepackage{graphicx}
\psfrag{a}{$x_1$}\psfrag{A}{$X_1$}
\psfrag{b}{$x_n$}\psfrag{B}{$X_n$}
\psfrag{c}{$y_n$}\psfrag{C}{$Y_n$}
\psfrag{d}{$y_1$}\psfrag{D}{$Y_1$}
\psfrag{y}{$y$}\psfrag{Y}{$Y$}\psfrag{z}{$z$}\psfrag{Z}{$Z$}\psfrag{x}{$x$}\psfrag{X}{$X$}
  \includegraphics[width=110mm]{fig3.eps}\\
  \caption{Path $P_W(x, y)$ connecting vertices $x$ and $y$. }
\end{center}
\end{figure}
Consider the tree $W$ in Fig. 3 with vertices $x$ and $y$, and
$$
P_W(x, y) = x_0(x)x_1 \ldots x_nzy_n \ldots y_1y_0(y)\ (x_0(x)x_1 \ldots x_ny_n \ldots y_1y_0(y))
$$
if $d_W(x, y)$ is even (odd) for any $n \geqslant 0$.
After the deletion of all the edges of $P_W(x, y)$ from $W$, some connected components
will be remained. Let $X_i\, (X_0)$ denote the component that contains $x_i\, (x_0 = x)$, let
$Y_i\, (Y_0)$ denote the component that contains $y_i\, (y_0 = y)$, for $i = 1, 2, \ldots , n$, and let $Z$
denote the component that contains $z$.
\begin{lemma}[\cite{20}]\label{lem2.2}
In the above situation, if $f_{X_i} (x_i) \geqslant f_{Y_i} (y_i)$ for $i = 0, 1, \ldots , n$, then
$f_W(x) \geqslant f_W(y)$. Furthermore, $f_W(x) = f_W(y)$ if and only if $f_{X_i} (x_i) = f_{Y_i} (y_i)$ for all
$i$.
\end{lemma}
If we have a tree $T$ with vertices $x$ and $y$, and two rooted
trees $X$ and $Y$, then we can build two new trees, first $T'$, by
identifying the root of $X$ with $x$ and the root of $Y$ with $y$,
second $T''$, by identifying the root of $X$ with $y$ and the root of
$Y$ with $x$ (as shown in Fig. 4).
\begin{figure}[h!]
\begin{center}
  % Requires \usepackage{graphicx}
\psfrag{a}{$T'$}\psfrag{b}{$T''$}\psfrag{T}{$T$}
\psfrag{y}{$y$}\psfrag{Y}{$Y$}\psfrag{x}{$x$}\psfrag{X}{$X$}
  \includegraphics[width=90mm]{fig4.eps}\\
  \caption{Switching subtrees rooted at $x$ and $y$.}
\end{center}
\end{figure}
\begin{lemma}[\cite{20}]\label{lem2.4}
In the above situation, if $f_T(x)> f_T(y), f_X(x)< f_Y(y)$, then we have $F(T'')> F(T')$.
\end{lemma}

Two distinct edges in a graph $G$ are \textit{independent} if they do not
have a common end vertex in $G$. A set of pairwise independent edges
of $G$ is called a \textit{matching} of $G$, while a matching of
maximum cardinality is a maximum matching of $G$. The \textit{matching number} $\beta$ of $G$ is the
cardinality of a maximum matching of $G$.
\begin{lemma}[\cite{28}]
Precisely the graph $T^n_\beta$ maximizes the total number of subtrees of $n$-vertex trees with matching number $\beta$, where $T^n_\beta$
is obtained from the star $K_{1,n-\beta}$ by adding $\beta-1$ pendant edges to $\beta-1$ leaves of $K_{1,n-\beta}$.
\end{lemma}
\begin{lemma}\label{lem2.10}
Consider a longest path $P_r=v_1v_2\ldots v_r$ in a tree $T$ with $r\ge 3,$ there exists a vertex $v_i \in V_{P_r}\setminus\{v_1, v_r\}$ such that
\begin{equation}\label{eq:2.3}
f_T(v_1)<\cdots < f_T(v_{i-1})< f_T(v_i)\geqslant f_T(v_{i+1})> \cdots >f_T(v_r).
\end{equation}
\end{lemma}
\begin{proof}
Choose three vertices $x, y, z$ such that $xy, yz \in E_T$. Let $X,
Y , Z$, respectively, denote the components containing $x, y, z$ after the removal of the edges $xy$ and $yz$
from $T$. Observe the identities:
\begin{eqnarray*}
% \nonumber to remove numbering (before each equation)
  f_T(x)&=&f_X(x)+ f_X(x)f_Y(y)+ f_X(x)f_Y(y)f_Z(z),\\
  f_T(z)&=&f_Z(z)+ f_Z(z)f_Y(y)+ f_Z(z)f_Y(y)f_X(x),\\
  f_T(y)&=&f_Y (y)+ f_X(x)f_Y(y)+ f_Z(z)f_Y(y)+f_X(x)f_Y(y)f_Z(z).
\end{eqnarray*}
This gives
\begin{equation}\label{eq:2.4}
2f_T(y)-f_T(x)-f_T(z) = 2f_Y(y)+(f_X(x)+ f_Z(z))(f_Y(y)-1)> 0.
\end{equation}
Let
\begin{equation}\label{eq:2.04}
 i:=\min\{j:\ 1\leqslant j\leqslant r,\, f_T(v_j)\geqslant f_T(u), \, u\in V_{P_r}\}.
\end{equation}
In view of (\ref{2.1}) and $f_T(v_2/v_1)>f_T(v_1/v_2)=1,
f_T(v_{r-1}/v_r)>f_T(v_r/v_{r-1})=1$, we can see that $i\not=1, r$.
By (\ref{eq:2.4}) and (\ref{eq:2.04}),  we have
$$
2f_T(v_{i+1})-f_T(v_i)-f_T(v_{i+2})> 0,\ \ f_T(v_i)\geqslant f_T(v_{i+1}).
$$
Hence,
$
f_T(v_i)\geqslant f_T(v_{i+1})>f_T(v_{i+2}).
$
Repeat the procedure as above to obtain
\begin{equation}\label{eq:2.5}
f_T(v_i)\geqslant f_T(v_{i+1})>f_T(v_{i+2})> \cdots >f_T(v_r).
\end{equation}

Similarly, we obtain
\begin{equation}\label{eq:2.6}
f_T(v_1)<\cdots < f_T(v_{i-1})< f_T(v_i).
\end{equation}
Hence, (\ref{eq:2.5}) and (\ref{eq:2.6}) imply (\ref{eq:2.3}) immediately.
\end{proof}

Let $T_1$ be the graph as depicted in Fig. 5, where $T'$ (resp. $T''$) is a tree with at least two vertices. Attaching a pendant edge to $u$ and contracting the edge $uv$ of $T_1$ yields the graph $T_2$; see Fig. 5.  We call the procedure constructing
$T_2$ from $T_1$ the $A$-\textit{transformation} of $T_1$.
\begin{figure}[h!]
\begin{center}
  % Requires \usepackage{graphicx}
  \psfrag{u}{$u$}\psfrag{t}{${\small\bullet}$} \psfrag{v}{$v$}\psfrag{d}{$T'$} \psfrag{e}{$T''$}
\psfrag{a}{$T_1$}\psfrag{b}{$T_2$}\psfrag{c}{$u=v$}\psfrag{k}{$\hat{T}_2$}
  \includegraphics[width=120mm]{fig5.eps}
  \caption{Trees $T_1$ and $T_2$.}
\end{center}
\end{figure}
\begin{lemma}\label{lem3.2}
Let $T_1$ and $T_2$ be the trees defined as above, we have $F(T_1)<F(T_2)$.
\end{lemma}
\begin{proof}
Let $\bar{T}$ be the component containing $v$ in $T_1-N_{T''}(v).$ Note that
$$
f_{\bar{T}}(u)-f_{\bar{T}}(v)=f_{\bar{T}}(u/v)-f_{\bar{T}}(v/u)=f_{\bar{T}}(u)-1>0,
$$
i.e., $
f_{\bar{T}}(u)>f_{\bar{T}}(v).$ Hence, by Lemma \ref{lem2.4} our result holds.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proofs of Theorems 1 and 2}

In this section, we first determine the extremal tree which minimizes the total number of subtrees among $\mathscr{T}_n^k$. Next we determine the extremal tree which maximizes (resp.  minimizes) the total number of subtrees among $\mathscr{P}_n^{p,q}$. \vspace{2mm}

\noindent{\bf Proof of Theorem 1.}\ \ Choose $T\in \mathscr{T}_n^k$
such that the total number of its subtrees is as small as possible. If $k=2$ or, $k=n-1$, it is easy to see that $\mathscr {T}_n^k=\{P_{n-k-1}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil)\}$, our result follows immediately. Hence, in what follows we consider $2<k<n-1$. In order to complete the proof, it suffices to show the following claims.

\begin{claim}
If $T$ minimizes the total number of subtrees in $\mathscr{T}_n^k,$ then $T\cong P_{n-k}(a,b),$ where $a \geqslant b \geqslant 1$ and $a+b=k$.
\end{claim}
\noindent{\bf Proof of Claim 11}\ \
If diam$(T)=3$, the claim follows immediately. Hence we consider the trees whose diameter is larger than 3.
Suppose that $P_r=v_1\ldots v_r\, (r \geqslant 5)$ is one of the longest paths in $T$, then we have
$d_T(v_3)=d_T(v_4)=\cdots =d_T(v_{r-2})=2$; otherwise set
$$
i:=\min\{j:\ d_T(v_j)\geqslant 3,\ v_j\in \{v_3, v_4, \ldots, v_{r-2}\}\}.
$$
and denote $N_T(v_i)=\{v_{i-1}, v_{i+1}, z_1,z_2,\ldots, z_s\},\ \  s\geqslant 1.$ Delete all the vertices $z_1,z_2,\ldots, z_s$ from $T$ and let $T_0$ be the component containing $v_i$. By Lemma \ref{lem2.10}, there exists $v_t\in V_{P_r}$ such that
$$
f_{T_0}(v_1)<\cdots < f_{T_0}(v_{t-1})< f_{T_0}(v_t)\geqslant f_{T_0}(v_{t+1})> \cdots >f_{T_0}(v_r).
$$

If $t< i,$ then  we have $f_{T_0}(v_i)>f_{T_0}(v_{r-1})$. By Lemma
\ref{lem2.4}, we have
\begin{equation}\label{eq:3.2}
 F(T) > F(T'),
\end{equation}
where
$T'=T-v_iz_1-\cdots -v_iz_s+v_{r-1}z_1+\cdots+v_{r-1}z_s.$

If $t \geqslant i,$ then  we have $f_{T_0}(v_i)>f_{T_0}(v_2)$. By Lemma
\ref{lem2.4}, we have
\begin{equation}\label{eq:3.3}
 F(T) > F(T''),
\end{equation}
where
$T''=T-v_iz_1-\cdots -v_iz_s+v_2z_1+\cdots+v_2z_s.$

Note that $T',\, T''\in \mathscr{T}_n^k,$ hence (\ref{eq:3.2}) (resp. (\ref{eq:3.3})) is a contradiction to the choice of $T$. This completes the proof of Claim 11.
\qed
\begin{claim}
Given positive integers $a,b$ with $a\geq b$ and $a+b=k,$ one has
\begin{equation}\label{eq:3.4}
F(P_{n-k}(a,b))=(2^a+2^b)(n-k-1)+2^k+k+{n-k-1\choose{2}}.
\end{equation}
Furthermore, if $a-b\geqslant 2$ then
\begin{equation}\label{eq:3.5}
F(P_{n-k}(a,b))> F(P_{n-k}(a-1,b+1)).
\end{equation}
\end{claim}
\noindent{\bf Proof of Claim 12}\ \
For convenience, assume that $d_{P_{n-k}(a,b)}(v_1)=a+1$ and $d_{P_{n-k}(a,b)}(v_{n-k})=b+1$. Then we have
\begin{equation}\label{eq:3.6}
\begin{split}
F(P_{n-k}(a,b))=&f_{P_{n-k}(a,b)}(v_1/v_{n-k})+f_{P_{n-k}(a,b)}(v_1*v_{n-k})+f_{P_{n-k}(a,b)}(v_{n-k}/v_1)\\
               &+F(P_{n-k}(a,b)-v_1-v_{n-k}).
\end{split}
\end{equation}

By direct calculation, we have
\begin{equation}\label{eq:3.7}
   \text{$f_{P_{n-k}(a,b)}(v_1/v_{n-k})=2^a(n-k-1)$\ \ \  and\ \ \ $f_{P_{n-k}(a,b)}(v_{n-k}/v_1)=2^b(n-k-1)$.}
\end{equation}
It is straightforward to check that the total number of subtrees of $P_{n-k}(a,b)$ containing both $v_1$ and $v_{n-k}$
is equal to the total number of subtrees of $K_{1,a+b}$ each contains the center of $K_{1,a+b}$. Hence, we have
\begin{equation}\label{eq:3.8}
f_{P_{n-k}(a,b)}(v_1*v_{n-k})=2^{a+b}=2^k.
\end{equation}

On the other hand,
\begin{equation}\label{eq:3.09}
F(P_{n-k}(a,b)-v_1-v_{n-k})=F((a+b)P_1\cup P_{n-k-2})=k+{n-k-1\choose{2}}.
\end{equation}
In view of (\ref{eq:3.6})-(\ref{eq:3.09}), (\ref{eq:3.4}) holds.
Hence,
$$
F(P_{n-k}(a,b))- F(P_{n-k}(a-1,b+1))=(2^a+2^b-2^{a-1}-2^{b+1})(n-k-1)=(2^{a-1}-2^b)(n-k-1).
$$
Note that $a-b\geqslant 2$, hence $(2^{a-1}-2^b)(n-k-1)>0$, i.e., $
F(P_{n-k}(a,b))>F(P_{n-k}(a-1,b+1))$, as desired.
\qed

By Claims 11 and 12, Theorem 1 follows immediately.\qed




\medskip
{\noindent\bf Proof of Theorem 2}\ \  For convenience, denote by $\iota(T)$ the number of non-pendant vertices of $T$. For any $T\in \mathscr{P}_n^{p,q}$. If $p=1$, $\mathscr{P}_n^{p,q}= \{K_{1,n-1}\}= \{D(1,n-1)\}=\{P_1(\lfloor\frac{n-1}{2})\rfloor,\lceil\frac{n-1}{2}\rceil\}$.
Our result holds in this case. Hence, in what follows, we consider $p\geqslant 2.$

First choose $T\in \mathscr{P}_n^{p,q}$
such that the total number of its subtrees is as large as possible. In order to characterize the structure of $T$,
it suffices to show that $\iota(T)=2.$

Note that when $p\ge 2$, hence $\iota(T)\not=1.$ So we assume to the contrary that $\iota(T)\geqslant 3.$
Choose three vertices, say $u,v,w$, such that each of them is of degree at least 2. Let $V_T=V_1\cup V_2$. It is straightforward to check that $\{u,v,w\}$ contains two elements in $V_1$ or $V_2$. We assume, without loss of generality, that $u,v \in V_1$ with $N_T(u)=\{u_1, z_1,\ldots ,z_t\}, N_T(v)=\{u_{2k-1}, r_1,\ldots ,r_s\}$, $t\geqslant 1,  s\geqslant 1$ and the unique path joining $u$ and $v$ is $P=uu_1\ldots u_{2k-1}v$. Consider the component in $T- uz_1- \cdots -uz_t- vr_1- \cdots- vr_s$, say $T'$, which contains both $u$ and $v$.

Without loss of generality, we assume $f_{T'}(u) \leqslant f_{T'}(v),$ then in view of (\ref{2.1}), we can see that $f_{T'}(u/v)\leqslant
f_{T'}(v/u)$. Let $T''$ be the component containing both $u$ and $v$ in the graph $T- uz_1- \cdots -uz_t,$ it is straightforward to see that
$$
   f_{T''}(u)-f_{T''}(v)=f_{T''}(u/v)-f_{T''}(v/u)=f_{T'}(u/v)-f_{T''}(v/u)<f_{T'}(u/v)-f_{T'}(v/u)\leqslant 0.
$$
i.e.,
\begin{equation}\label{eq:4.1}
f_{T''}(u) < f_{T''}(v).
\end{equation}
Let
$$
 T^*=T- uz_1-uz_2- \cdots -uz_t+vz_1+vz_2+\cdots+ vz_t.
$$
Note that $u$ and $v$ are in $V_1$, hence we have
$T^* \in \mathscr{P}_n^{p,q}$. On the other hand, by (\ref{eq:4.1}) and Lemma
\ref{lem2.4}, we have $F(T)< F(T^*)$, a contradiction to the choice
of $T$.
Hence, we get that $\iota(T)=2$, i.e., $T\cong D(p,q),$ as desired.\vspace{2mm}

Now choose $T\in \mathscr{P}_n^{p,q}$
such that the total number of its subtrees is as small as possible. If $p=q$ or
$p=q-1$, it is easy to see that $P_n\in \mathscr{P}_n^{p,q}$, as
$P_n$ minimizes the total number of subtrees of $n$-vertex tree, we can
see that $P_n=P_{2p-1}(1,1)$ or $P_n=P_{2p-1}(0,1),$ minimizes the
total number of subtrees among $\mathscr{P}_n^{p,q}$. Hence, in what
follows we consider $1<p< \lfloor\frac{n}{2}\rfloor$. In order to
complete the proof, it suffices to show the following claim.
\begin{claim}
If $T$ minimizes the total number of subtrees of trees in $\mathscr{P}_n^{p,q},$ then $T\cong P_{2p-1}(a,b)$, where $a+b=n-2p+1$ with $a \geqslant b \geqslant 1.$
\end{claim}
\noindent{\bf Proof of Claim 13}\ \
If $1<p< \lfloor\frac{n}{2}\rfloor$, it is easy to see that $T \not \cong D(p,q)$, so diam$(T) \geqslant 3$. If diam$(T)=3$, the claim follows immediately. Hence in what follows we consider the trees whose diameter is larger than 3.
Suppose that $P_r=v_1\ldots v_r\, (r \geqslant 5)$ is one of the longest paths in $T$, we are to show that
$d_T(v_3)=d_T(v_4)=\cdots =d_T(v_{r-2})=2$ and $r=2p+1$. First assume to the contrary that there exists a vertex $v\in \{v_3, v_4, \ldots,v_{r-2}\}$ such that
$d_T(v)\geqslant 3.$ Let
$$
i=\min\{j:\ d_T(v_j)\geqslant 3,\ \ \ 3\leqslant j \leqslant r-2\},\ \ \ \ N_T(v_i)=\{v_{i-1}, v_{i+1}, z_1,z_2,\ldots, z_s\},\ \  s\geqslant 1.
$$
Let $T_0$ be the component that contains $v_i$ in $T-\{z_1,z_2,\ldots, z_s\}$. By Lemma \ref{lem2.10}, there exists $v_t\in V_{P_r}$ such that
$$
f_{T_0}(v_1)<\cdots < f_{T_0}(v_{t-1})< f_{T_0}(v_t)\geqslant f_{T_0}(v_{t+1})> \cdots >f_{T_0}(v_r).
$$
If $t< i,$ then we have
$f_{T_0}(v_i)>f_{T_0}(v_{r-1})>f_{T_0}(v_r)$. If $v_i$ and $v_{r-1}$
are in the same part, by Lemma \ref{lem2.4}, we have
\begin{equation}\label{eq:4.2}
 F(T) > F(T'),
\end{equation}
where
$$T'=T-v_iz_1-\cdots -v_iz_s+v_{r-1}z_1+\cdots+v_{r-1}z_s,\ \ \ \ T'\in \mathscr{P}_n^{p,q}$$
otherwise, $v_i$ and $v_r$ are in the same part, we have
\begin{equation}\label{eq:4.3}
 F(T) > F(T''),
\end{equation}
where
$$T''=T-v_iz_1-\cdots -v_iz_s+v_rz_1+\cdots+v_rz_s,\ \ \ \ T''\in \mathscr{P}_n^{p,q}.$$
If $t \ge i$, repeat the procedure as above, we have a $T'''\in \mathscr{P}_n^{p,q}$ such that
\begin{equation}\label{eq:4.4}
 F(T) > F(T'''),\ \ \ \ T'''\in \mathscr{P}_n^{p,q}.
\end{equation}
Hence, (\ref{eq:4.2})-(\ref{eq:4.4}) are contradictions to the choice of $T$. So we have $T\cong P_{r-2}(a,b)$.

Notice that $T\in \mathscr{P}_n^{p,q}$ with
$1<p<\lfloor\frac{n}{2}\rfloor$, it is easy to see that $r \leqslant
2p+1$. If $r< 2p+1$, it means that $v_1$ and $v_r$ are in different
parts (otherwise we have $p< \lceil\frac{r-2}{2}\rceil$ or $q<
\lceil\frac{r-2}{2}\rceil$). As $a \geqslant b$, we have $v_1 \in V_2$ and
$v_r\in V_1$, where $V_1$ and $V_2$ are two parts of $V_T$ with
$|V_1|=p, |V_2|=q$. Assume that $N_T(v_2)=\{v_3,v_1, w_2,\ldots,
w_{a}\}, N_T(v_{r-1})=\{v_{r-2},v_r, u_2,\ldots, u_{b}\}$. Let
$\hat{T}=T-\{v_r, u_2,\ldots, u_b\}$. By Lemma \ref{lem2.2}, we have
$f_{\hat{T}}(v_{r-1}) < f_{\hat{T}}(v_1)$. Hence, in view of Lemma
\ref{lem2.4} we have
\begin{equation}\label{eq:4.5}
 F(T) > F(\tilde{T}),
\end{equation}
where
$
  \tilde{T}=T-v_{r-1}v_r-v_{r-1}u_2-\cdots -v_ru_b+v_1v_r+v_1u_2+\cdots+v_1u_b.
$
Note that $v_{r-1}, v_1\in V_2$, $\tilde{T}\in \mathscr{P}_n^{p,q}$, hence (\ref{eq:4.5}) is a contradiction to the choice of $T$. So we have $T\cong P_{2p-1}(a,b)$.
\qed

Combining with Claims 12 and 13, we have $T\cong P_{2p-1}(\lfloor\frac{n-2p+1}{2}\rfloor, \lceil\frac{n-2p+1}{2}\rceil)$, as desired.
\qed

\begin{remark} By direct calculation, we have
$$
F(D(p,q))=2^{n-2}+2^{p-1}+2^{q-1}+n-2.
$$
This gives
$$
F(D(p,q))-F(D(p-1,q+1))=2^{p-2}-2^{q-1}<0
$$
for $1<p \leqslant q$. Hence, we have
\begin{equation}\label{eq:4.6}
F(D(p,q))< F(D(p-1,q+1))< \cdots< F(D(1,n-1))=F(K_{1,n-1}),
\end{equation}
for $1<p \leqslant q$. Note that $D(p,q)$ maximizes the total number of subtrees among $\mathscr{P}_n^{p,q}$, hence in view of (\ref{eq:4.6}) and first part of Theorem 2, the following corollary holds immediately.
\end{remark}
\begin{corollary}[\cite{21}]
The star $K_{1,n-1}$ has $2^{n-1}+n-1$ subtrees, more than any other tree on $n$ vertices.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof of Theorem 3}
In this section we determine the extremal tree which minimizes the the total number of subtrees among $\mathscr{A}_n^q$.\vspace{2mm}

\noindent{\bf Proof of Theorem 3}\ \
In order to characterize the structure of the tree, say $T$, minimizing the total number of subtrees in $\mathscr{A}_n^q,$
it suffices to show that the diameter of $T$ is $n+1$. Without loss of generality, we assume one of the longest paths in $T$ is $P_{r+1}=v_0 v_1\ldots v_r$. If $r=n+1$, our result holds obviously. So in what follows, we assume that $r\le n.$

For convenience, let $T_i$ be the component that contains $v_i$ in $T-E_{P_{r+1}}$ for $i=1, 2, \ldots r-1$. Set
$$
l:=\min\{i:\ 1\leqslant i \leqslant r-1, T_i\not\cong K_{1, q-2}\}.
$$
We can see that there exists $j\in \{1,2,\ldots, q-2\}$ such that $d_T(v_{lj})>1$, i.e., $d_T(v_{lj})=q$. Note that $P_{r+1}$ is a longest path in $T$, hence
$$\label{eq:5.2}
1 <l <r-1.
$$
Thus, we can partition $T$ into two subtrees, say $S$ and $T_0$, such that $E_T=E_S\cup E_{T_0}, V_T=V_S\cup V_{T_0}$ and $V_S\cap V_{T_0}=\{v_{l_j}\};$ see Fig. 6. For convenience, let $N_{T_0}(v_{l_j})=\{w_1, w_2, \ldots, w_{q-1}\}.$
\begin{figure}[h!]
\begin{center}
  % Requires \usepackage{graphicx}
  \psfrag{0}{$v_0$}\psfrag{1}{$v_1$}\psfrag{2}{$v_2$}\psfrag{s}{$S$}
  \psfrag{l}{$v_l$}\psfrag{n}{$v_{r-1}$}\psfrag{c}{$v_r$}
  \psfrag{m}{$v_{l_j}$}\psfrag{e}{$T_0$}
\psfrag{d}{$q-2$}
  \includegraphics[width=70mm]{fig6.eps}\\
  \caption{A $q$-arc tree $T$.}
\end{center}
\end{figure}


Now we are in the position to apply Lemma \ref{lem2.2} in the following setting:
$$
x\leftarrow v_0, \ x_1\leftarrow v_1, \ldots, y_1\leftarrow v_l, y\leftarrow v_{l_j}.
$$
It is easy to see that
$$
f_{X_i}(x_i)= f_{Y_i}(y_i)=2^{q-2}, \ \ \ \ i = 2, \ldots , \lfloor l/2\rfloor
$$
and $f_{Y_1}(y_1)>2^{q-2}=f_{X_1}(x_1)$. Therefore, by Lemma \ref{lem2.2}, we have
$f_S(x) < f_S(y),$
where $S$ is defined as above. By Lemma \ref{lem2.4}, we
have
\begin{equation}\label{eq:5.3}
F(T')< F(T),
\end{equation}
where
$
 T'=T-\{v_{l_j}w_1, v_{l_j}w_2,\ldots, v_{l_j}w_{q-1}\}+\{v_0w_1, v_0w_2,\ldots, v_0w_{q-1}\}.
$
Inequality (\ref{eq:5.3}) is a contradiction to the choice of $T$. Hence, we obtain $r= n+1$, i.e., $T\cong \hat{T}_n^q,$ as desired.
\qed

\begin{remark} In particular, let $q=3$ in Theorem 3, we can obtain that just the $n$-leaf binary caterpillar tree
minimizes the total number of subtrees among $n$-leaf binary trees, which is obtained by
Sz\'ekely and Wang {\rm\cite{21}}.
\end{remark}
\begin{corollary}[\cite{21}]
For any $n \ge 2$, precisely the $n$-leaf binary caterpillar tree $\hat{T}_{n-2}^3$ minimizes the number of subtrees among $n$-leaf binary trees.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof of Theorems 4 and 5}%\setcounter{equation}{0}
In this section we determine the extremal $n$-vertex tree with domination number $\gamma$ maximizing the total number of subtrees. Furthermore, the extremal $n$-vertex tree with domination number $\frac{n}{2}$ minimizing the total number of subtrees is also characterized.\medskip

\noindent{\bf Proof of Theorem 4} \ \
It is known from \cite{x-k-f} that $\gamma(G)\leqslant \beta(G),$ where $\beta(G)$ is the matching number of $G$. In what follows we are to show:
If $T_0\in \mathscr{D}_n^\gamma$ maximizes the total number of subtrees, then $\gamma(T_0)=\beta(T_0)$.

In fact, it suffices to show that $\gamma(T_0)\geqslant \beta(T_0)$. Otherwise, by the definition of the set $\mathscr{D}_n^\gamma$, we have $\beta(T_0) > \gamma(T_0) =\gamma$. Assume that $S =\{v_1, v_2, \ldots, v_{\gamma} \}$ is a dominating set of cardinality $\gamma$. Then there exist $\gamma$ independent edges
$v_1v_1', v_2v_2',\ldots, v_{\gamma}v_{\gamma}'$ in $T_0$. Note that $\beta(T_0) > \gamma(T_0) = \gamma$, there must exist another edge, say $w_1w_2$, which is independent of each of edges $v_iv_i'$,\, $i = 1, 2, \ldots, \gamma$.
\begin{figure}[h!]
\begin{center}
  % Requires \usepackage{graphicx}
\psfrag{a}{$v_1$}\psfrag{b}{$v_2$}\psfrag{c}{$v_1'$}\psfrag{d}{$v_2'$}
\psfrag{e}{$w_1$}\psfrag{f}{$w_2$}\psfrag{g}{$v_{\gamma}$}\psfrag{h}{$v_{\gamma}'$}\psfrag{A}{$T_0$}
  \psfrag{B}{$T_0'$}
  \includegraphics[width=120mm]{fig7.eps}\\
  \caption{The structures of $T_0$ and $T_0'$ in the proof of Theorem 4.}
\end{center}
\end{figure}

If the two vertices $w_1, w_2$ are dominated by the same vertex $v_i \in S$, then a triangle $C_3 = w_1w_2v_i$
occurs. This is impossible because of the fact that $T_0$ is a tree. Therefore $w_1, w_2$ are dominated by two different vertices from $S$.
Without loss of generality, assume that $w_i$
is dominated by the vertex $v_i$ for $i = 1, 2$ (see Fig. 7). Now we construct a new tree $T_0'\in \mathscr{D}_n^\gamma$ by
$A$-transformation of $T_0$ on the edges $v_1w_1$ and $v_2w_2$, respectively. By Lemma \ref{lem3.2}, we have $F(T_0)< F(T_0')$, a contradiction.
Thus, Theorem 4 follows immediately from Lemma 8.

This completes the proof.\qed\vspace{2mm}

\noindent{\bf Proof of Theorem 5} \ \  It is known \cite{3,13} that if $n=2\gamma$, then a tree $T$ belongs to $\mathscr{D}_n^\gamma$ if and only if there exists a tree $H$ on $\gamma=\frac{n}{2}$ vertices such that $T = H\circ K_1$, where $H\circ K_1$ is obtained by attaching a leaf to each vertex of $H$. Hence in what follows, we are to show:
For any tree $T,$ one has
$
F(T\circ K_1)\geqslant F(P_{|V_T|}\circ K_1)
$
with equality if and only if $T\cong P_{|V_T|}.$

In fact, let $\mathscr{R}(T)$ be the set of all the subtrees of tree $T$.
For any $u$ in $V_T$ and $1\leqslant m\leqslant |V_T|$,
let $\mathscr{R}^m(T; u)$ denote the set of all $m$-vertex subtrees of a tree $T$ each of which contains $u.$ It is routine to check that
\begin{eqnarray}
% \nonumber to remove numbering (before each equation)
  F(T\circ K_1)&=& \sum_{T_1\in \mathscr{R}(T)}2^{|V_{T_1}|}+|V_T|\label{eq:4.02} \\
  &=& \sum_{T_1\in \mathscr{R}(T-u)}2^{|V_{T_1}|}+\sum_{T_1\in \mathscr{R}(T;u)}2^{|V_{T_1}|}+|V_T| \notag\\
               &=& \sum_{T_1\in \mathscr{R}(T-u)}2^{|V_{T_1}|}+\sum_{m=1}^{|V_T|}|\mathscr{R}^m(T;u)|2^m+|V_T|.\label{eq:4.???}
\end{eqnarray}

Assume that $T\not\cong P_{|V_T|}$. If $|V_T|=2$ or $3$, our result is clearly true. If $|V_T|= 4$, there exist only two
trees, i.e., $P_4$ and $K_{1,3}$, hence $T=K_{1,3}$. In this case, for any $u\in PV(T)$ we have
\begin{equation}\label{eq:4.7}
    |\mathscr{R}^1(T;u)|=|\mathscr{R}^2(T;u)|=|\mathscr{R}^4(T;u)|=1, |\mathscr{R}^3(T;u)|=2
\end{equation}
And for any $v\in PV(P_4)$, we have
\begin{equation}\label{eq:4.8}
    |\mathscr{R}^1(P_4;v)|=|\mathscr{R}^2(P_4;v)|=|\mathscr{R}^3(P_4;v)|=|\mathscr{R}^4(P_4;u)|=1.
\end{equation}
Note that $P_4-u=K_{1,3}-v$, hence by (\ref{eq:4.???})-(\ref{eq:4.8}) we have
$
F(K_{1,3}\circ K_1)>F(P_4\circ K_1).
$

In what follows we assume that $F(T\circ K_1) > F(P_{|V_T|}\circ K_1)$ holds for all trees of order less than $|V_T|$. On the one hand, for any $u\in PV(T)$ and $v\in PV(P_{|V_T|})$, we have
\begin{equation}\label{eq:0009}
F((T-u)\circ K_1)\geqslant F((P_{|V_T|}-v)\circ K_1),
\end{equation}
Each of the equalities in (\ref{eq:0009}) holds if and only if $T-u\cong P_{|V_T|}-v$.
Hence by (\ref{eq:4.02}), we have
\begin{equation}\label{4.9}
\sum_{T_1\in \mathscr{R}(T-u)}2^{|V_{T_1}|}\geqslant \sum_{T_1\in \mathscr{R}(P_{|V_T|}-v)}2^{|V_{T_1}|}.
\end{equation}
On the other hand, it is easy to see that for any $w\in PV(T)\setminus \{u\}$, $T-w\in \mathscr{D}^{|V_T|-1}(T;u)$, so we have
\begin{equation}\label{4.10}
   |\mathscr{R}^{|V_T|-1}(T;u)|>1=|\mathscr{R}^{|V_T|-1}(P_{|V_T|};v)|.
\end{equation}
Furthermore, for $m=1,2,\ldots, |V_T|-2, |V_T|$,
\begin{equation}\label{4.11}
   |\mathscr{R}^{m}(T;u)|\geqslant 1=|\mathscr{R}^{m}(P_{|V_T|};v)| .
\end{equation}
Hence, $F(T\circ K_1)> F(P_{|V_T|}\circ K_1)$ follows by (\ref{eq:4.3}) and (\ref{4.9})-(\ref{4.11}) for $T\not\cong P_{|V_T|}$.


This completes the proof.
\qed

\section*{Acknowledgments}
The authors would like to express their sincere gratitude to the referee
for his/her careful reading of the paper and for all the insightful comments
and valuable suggestions, which considerably improved the presentation of this paper.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file


\begin{thebibliography}{99}

\bibitem{B-M-G}J.A. Bondy, U.S.R. Murty, Graphs Theroy. Springer, New York (2008)
%\bibitem{2} A.V. Aho, N.J.A. Sloane, Some doubly exponential sequences, Fibonacci Quart. 11 (4) (1973) 429-437.

%\bibitem{16}C. Delorme, O. Favaron, D. Rautenbach, On the Randi\'c index, Discrete Math. 257 (2002) 29-38.

\bibitem{15} A.A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (3) (2001) 211-249.

\bibitem{3}J.F. Fink, M.S. Jocobson, L.F. Kinch, J. Roberts, On graphs having domination number half their order, Period. Math. Hungar.
16 (1985) 287-293.

%\bibitem{3G}I. Gutman, S.J. Cyvin, Kekul\'e, Structures in Benzenoid Hydrocarbons, Springer, Berlin, 1988.

%\bibitem{4}M. Fischermann, A. Hoffmann, D. Rautenbach, L.A. Sz\'ekely, L. Volkmann, Wiener index versus maximum
%degree in trees, Discrete Appl. Math. 122 (1-3) (2002) 127-137.

\bibitem{H-C-X}C.X. He, B.F. Wu, Z.S. Yu, On the energy of trees with given domination number,
MATCH Commun. Math. Comput. Chem. 64 (1) (2010) 169-180.

%\bibitem{5}F. Jelen, E. Triesch, Superdominance order and distance of trees with bounded maximum degree, Discrete
%Appl. Math. 125 (2-3) (2003) 225-233.

%\bibitem{6}C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185-190.

\bibitem{19}R. Kirk, H. Wang, Largest number of subtrees of trees with a given maximum degree, SIAM J. Discrete Math. 22 (3) (2008) 985-995.

%\bibitem{7}B. Knudsen, Optimal multiple parsimony alignment with affine gap cost using a phylogenetic tree, in: Lecture
%Notes in Bioinformatics, vol. 2812, Springer-Verlag, 2003, pp. 433-446.

%\bibitem{8}L. Lov\'asz, Combinatorial Problems and Exercises, second ed., North-Holland, Amsterdam, 1993.

%\bibitem{9}The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/~njas/sequences/.

%\bibitem{24}D. Rautenbach, A note on trees of maximum weight and restricted degrees, Discrete Math. 271 (2003) 335-342.

\bibitem{S-C-W}C.W. Song, Counting special families of labelled trees, Ann. Comb. 10 (2) (2006) 271-283.

\bibitem{20}L.A. Sz\'ekely, H. Wang, Binary trees with the largest number of subtrees, Discrete Appl. Math. 155 (3) (2007) 374-385.

\bibitem{02}L.A. Sz\'ekely, H. Wang, On subtrees of trees, 2004 Industrial Mathematics Institute Research Reports 04:04, University of South Carolina,
    \url{http://www.math.sc.edu/~imip/04.html}, 2004.

\bibitem{03}L.A. Sz\'{e}kely, H.Wang, Binary trees with the largest number of subtrees with at least one leaf, Congr. Numer. 177 (2005) 147-169.

\bibitem{21}L.A. Sz\'ekely, H. Wang,  On subtrees of trees, Adv.  Appl. Math. 34 (1) (2005) 138-155.

\bibitem{S-W-W} L. A. Sz\'ekely, H. Wang, T.Y. Wu, The sum of the distances between the leaves of a tree and
the `semi-regular' property, Discrete Math. 311 (13) (2011) 1197-1203.

\bibitem{17}A. Vince, H. Wang, The average order of a subtree of a tree, J. Combin. Theory Ser. B 100 (2) (2010) 161-170.

%\bibitem{22}H. Wang, Extremal trees with given degree sequence for the Randi\'c index, Discrete Math. 308 (2008) (15) 3407-3411.


\bibitem{W-W-W}S. Wagner, Correlation of graph-theoretical indices, SIAM J. Discrete Math. 21 (1) (2007) 33-46.

\bibitem{18}H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, Discrete Appl. Math. 156 (14) (2008) 2647-2654.

\bibitem{12}H. Wang, Some results on trees, PhD Thesis, Department of Mathematics, University of South Carolina,
2005.

%\bibitem{14}H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17-20.

\bibitem{13} B. Xu, E.J. Cockayne, T.W. Haynes, S.T. Hedetniemi, S.C. Zhou, Extremal graphs for inequalities involving domination
parameters, Discrete Math. 216 (2000) 1-10.

\bibitem{x-k-f}K.X. Xu, L.H. Feng, Extremal energies of trees with a given domination
number, Linear Algebra Appl. 435 (2011) 2382-2393.

\bibitem{25}W.G. Yan, Y.N. Ye, Enumeration of subtrees of trees,  Theoret. Comput. Sci. 369 (2006) 256-268.

\bibitem{Y-L-Z}L.Z. Ye, R.S. Chen, Ordering of trees with a given bipartition by their energies and Hosoya indices, MATCH Commun. Math. Comput. Chem. 52 (2004) 193-208.

%\bibitem{13} H. Zelinka, Medians and peripherians of trees, Arch. Math. (Brno) 4 (1968) 87-95.

\bibitem{26}X.D. Zhang, Y. Liu, M.X. Han, Maximum Wiener index of trees with given degree sequence, MATCH Commun. Math. Comput. Chem. 64 (3) (2010) 661-682.

\bibitem{27}X.D. Zhang, Q.Y. Xiang, L.Q. Xu, R.Y. Pan, The Wiener index of trees with given degree sequences, MATCH Commun. Math. Comput. Chem. 60 (2) (2008) 623-644.
\bibitem{270}X.M. Zhang, X.D. Zhang, Trees with given degree sequences that have minimal subtrees, arXiv:submit/0543782 [math.CO] 3 Sep 2012.
\bibitem{28}X.M. Zhang, X.D. Zhang, D. Gray, and H. Wang, The number of subtrees of trees with given degree sequence, Journal of Graph Theory (2012): DOI 10.1002/jgt.
\bibitem{29}X.M. Zhang, X.D. Zhang, D. Gray, and H. Wang, Trees with the most subtrees-- an algorithmic
approach, J. Comb. 3 (2) (2012) 207-223.
\end{thebibliography}
\end{document}

