\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P67}{20(1)}{2013}
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage{epsf}
\usepackage{url,rotating}
%\usepackage[cp1250]{inputenc}
%\usepackage{amsthm,amsmath,amssymb}
\usepackage{amsmath,amsfonts,amssymb,latexsym}
\usepackage[left=2cm,top=2cm,right=2cm,bottom=4cm,nohead]{geometry}
%\usepackage[notref,notcite]{showkeys}
\usepackage{setspace}
\usepackage{enumitem}
\usepackage{multirow}
%\doublespacing
%\listfiles
\renewcommand{\theequation}{\thesection.\arabic{equation}}

%\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{claim}{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

%\theoremstyle{definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{task}[theorem]{Task}

%\theoremstyle{remark}
\newtheorem{rem}{Remark}
%\newtheorem{theorem}{Theorem}

%\def\vt{t\kern-0.22em\raise.18ex\hbox{\char'47}\lower.18ex\hbox{}\kern-0.08em}
%\newcommand{\old}[1]{{}}
%\newcommand{\mnote}[1]{\marginpar{\raggedright\footnotesize\em#1}}%Marginal Note


\title{Extremal values of ratios:\\ 
distance problems vs. subtree problems in trees}


\author{L\'aszl\'o A. Sz\'ekely\thanks{This 
author acknowledges financial support from the grant \#FA9550-12-1-0405 from the U.S.
Air Force Office of Scientific Research (AFOSR) and the Defense Advanced
Research Projects Agency (DARPA) and from the  grant 1000475 of the NSF DMS.}\\
\small Department of Mathematics,\\[-0.8ex]
\small  University of South Carolina\\[-0.8ex]
\small Columbia, SC 29208, USA\\
\small\tt szekely@math.sc.edu\\
\and 
Hua Wang\thanks{This 
author acknowledges financial support from the grant 245307 from the Simons Foundation. }\\
\small Department of Mathematical Sciences,\\[-0.8ex]
\small Georgia Southern University\\[-0.8ex]
\small Statesboro, GA 30460, USA\\
\small\tt hwang@georgiasouthern.edu
}



% switch to manual footnotes to avoid pre-superscript on AMS
%\renewcommand{\thefootnote}{}
%\footnotetext{{\em AMS Subject Classification (2010)}\/:\   05C05; 05C12; 05C35; 92E10 \\{\em Keywords:~} Wiener index; tree; 
%binary tree; caterpillar; star tree; good binary tree; distances in trees; subtrees of trees; extremal problems; center; centroid; subtree core  }

%\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%\footnotetext[2]
%\footnotetext[3]{Current address: Department of Mathematics, Simon Fraser University, Burnaby, B.~C.}

\newcommand\bw{{\operatorname{bw}}}
\newcommand\bwe[3]{{\bw_e(#1,#2;#3)}}
\newcommand\bweGWa{{\bwe{G}{W}{\alpha}}}
\newcommand\Bwe[2]{{\bw_e(#1,#2)}}

\newcommand\bwv[2]{{\bw_v(#1;#2)}}
\newcommand\bwvGa{{\bwv{G}{\alpha}}}
\newcommand\Bwv[1]{{\bw_v(#1)}}

\newcommand\bwV[2]{{\bw_v^\ast(#1;#2)}}
\newcommand\bwVGa{{\bwV{G}{\alpha}}}
\newcommand\BwV[1]{{\bw_v^\ast(#1)}}


\date{\dateline{Dec 28, 2012}{Mar 18, 2013}{Mar 24, 2013}\\
\small Mathematics Subject Classifications: 05C05, 05C12, 05C35, 92E10}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Author's definitions


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\bfloor}[1]{\bigg\lfloor{#1}\bigg\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}



\newcommand{\DEF}[1]{{\em #1\/}}
\newcommand{\dfnc}[3]{#1:#2\rightarrow #3}
\newcommand{\dset}[2]{\left\{#1 \:|\: #2\right\}}
\newcommand{\lset}[2]{\left\{#1, \ldots, #2\right\}}
\newcommand{\POZOR}[1]{{\bf #1\/}}
\newcommand{\os}[1]{\omega(#1,\Sigma)} 
\newcommand{\Fs}[1]{F(#1,\Sigma)} 
\newcommand{\osk}{\os{k}} 
\newcommand{\Fsk}{\Fs{k}} 
\newcommand{\dsp}{\displaystyle}

\newcommand{\cov}{\operatorname{cov}}
\newcommand{\var}{\operatorname{var}}
\newcommand{\crn}{\operatorname{cr}}
\newcommand{\crs}[1]{\operatorname{cr}(#1,\Sigma)}
\newcommand\Mcrn{{\operatorname{Mcr}}}
\newcommand\mcrn{{\operatorname{mcr}}}
\newcommand\scrn{{\operatorname{scr}}}
\newcommand\mcrs[1]{{\mcrn(#1,\Sigma)}}
\newcommand\scrs[1]{{\scrn(#1,\Sigma)}}
\newcommand\Mcrs[1]{{\Mcrn(#1,\Sigma)}}
\newcommand{\RR}{\mbox{$\mathbb R$}}
\newcommand{\NN}{\mbox{$\mathbb N$}}
\newcommand{\QQ}{\mbox{$\mathbb Q$}}
\newcommand{\ZZ}{\mbox{$\mathbb Z$}}
\renewcommand{\SS}{\mbox{$\mathbb S$}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cP}{{\cal P}}
\newcommand{\eopf}{\raisebox{0.8ex}{\framebox{}}}
\newcommand{\dist}{\hbox{\rm d}}
\renewcommand\a{\alpha}
\renewcommand\b{\beta}
\renewcommand\c{\gamma}
\renewcommand\d{\delta}
\renewcommand\o{\omega}
\newcommand\D{\Delta}
\newcommand{\thx}{\vartheta}
\newcommand{\phx}{\varphi}
\newcommand{\epx}{\varepsilon}
\newcommand{\directedE}{\mbox{$\vec{E}$}}
\newcommand{\directedchi}{\mbox{$\vec{\chi}$}}
\newcommand{\directedchic}{\mbox{$\vec{\chi}_c$}}
\newcommand{\directedplus}{\,\vec{+}\,}
\newcommand{\sq}{\,\Box\,}


\newcommand{\MG}{{\bar{G}}}
\newcommand{\MD}{{\bar{D}}}
\newcommand{\MP}{{\bar{P}}}
\newcommand{\Mo}{{\bar{\omega}}}
\newcommand{\Ml}{{\bar{\lambda}}}
\newcommand{\ML}{{\bar{\Lambda}}}
\newcommand{\hD}{{\hat{D}}}
\newcommand{\hG}{{\hat{G}}}
\newcommand{\dig}{\mbox{{\rmfamily\upshape digirth}}}
\newcommand{\bn}{\bigskip\noindent}

\newcommand{\R}{R_{\vec{G}}}
\newcommand{\W}{W_{\vec{G}}}
\newcommand{\B}{B_{\vec{G}}}


\newenvironment{proof}%
{\noindent{\bf Proof.}\ }%
{\hfill\eopf\par\bigskip}%

\newenvironment{proofof}[1]%
{\noindent{\bf Proof of #1.}\ }%
{\hfill\eopf\par\bigskip}%

\newenvironment{sproof}%
{\noindent{\bf Sketch of a proof.}\ }%
{\hfill\eopf\par\bigskip}%

\newenvironment{pproof}%
{\noindent{\bf Proof in progress.}\ }%
{\hfill\eopf\par\bigskip}%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

\maketitle

\begin{abstract}
The authors discovered a dual behaviour of two tree indices, the Wiener index and the number
of subtrees, for a number of extremal problems  [{\em Discrete Appl. Math.}  {\bf 155} (3) 2006,  374--385;  {\em Adv. Appl. Math.} {\bf 34} (2005), 138--155].
 Barefoot, Entringer and Sz\'ekely [{\em Discrete Appl. Math.} {\bf 80}(1997), 37--56]
  determined extremal values of
 $\sigma_T(w)/\sigma_T(u)$,   $\sigma_T(w)/\sigma_T(v)$, $\sigma(T)/\sigma_T(v)$,
       and $\sigma(T)/\sigma_T(w)$, 
where $T$ is a tree on $n$ vertices, $v$ is in the centroid
   of the tree $T$, and $u,w$ are leaves in $T$. 
   In this paper  we test how far the negative correlation between
   distances and subtrees go if we look for the   extremal values
   of $F_T(w)/F_T(u)$, $F_T(w)/F_T(v)$, $F(T)/F_T(v)$,  
   and $F(T)/F_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the subtree core
   of the tree $T$, and $u,w$ are leaves in $T$---the complete analogue, % of  \cite{barefoot}, 
    changing distances to the number of subtrees.  We include a number of open problems,
    shifting the interest towards the number of subtrees in graphs.

\bigskip
 
\noindent \textbf{Keywords:} Wiener index; tree; binary tree; caterpillar; star tree; good binary tree; distances in trees; subtrees of trees; extremal problems; center; centroid; subtree core.
\end{abstract}

%\eject
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Motivation}
\subsection{Results for the Wiener index}

In chemical graph theory, the Wiener index  is a topological index of a molecule, defined as the sum of the numbers of edges in the shortest paths in a chemical graph between all pairs of non-hydrogen atoms in a molecule. Since 1947, when H. Wiener introduced this index \cite{wiener}  noting its correlation  with
boiling temperatures of paraffins, this index has turned into a frequently used graph parameter.

This paper is concerned with trees, i.e. connected and cycle-free graphs. In a tree $T$, for vertices 
$u,v\in V(T) $ let $d_T(u,v)$ denote the {\em distance} of the vertices, i.e. the number of edges in the
unique $uv$ path in $T$. The {\em distance of vertex $w$},   $\sigma_T(w)$, is defined as 
$\sum_{v\in V(T)} d_T(w,v)$, and the {\em Wiener index of the tree $T$,} $\sigma(T)$, is defined as $\frac{1}{2} \sum_w 
\sigma_T(w)$. For a survey on the Wiener index of trees, see \cite{gutman}. We term degree 1 vertices in a tree as {\em leaves}.  A tree is {\em binary},
if  the degree of every vertex is 1 or 3. A {\em caterpillar tree} has a path from which the distance of every vertex is at most 1. A {\em complete binary tree} has an edge $uv$, from which all leaves have the
same distance. A {\em good tree} is complete binary tree, or comes from a complete binary tree
by deletion of some leaves in the following way. Make a planar (crossing-free) drawing  of the complete binary tree such that the special $uv$ edge is on top, and delete some pairs of leaves such that the deleted pairs of leaves make an
initial segment   in  the left-to-right order among the leaves.
%\mnote{counterclockwise turned meaningless!}  
\begin{figure}[h]
\setlength{\unitlength}{3pt}
\begin{picture}(110,22)
%\put(30,17){\circle*{1}} \put(20,12){\circle*{1}}
%\put(40,12){\circle*{1}} \put(15,7){\circle*{1}}
%\put(25,7){\circle*{1}} \put(35,7){\circle*{1}}
%\put(45,7){\circle*{1}} \put(48,2){\circle*{1}}
%\put(42,2){\circle*{1}}

%\put(30,17){\line(-2,-1){10}} \put(30,17){\line(2,-1){10}}
%\put(20,12){\line(-1,-1){5}} \put(20,12){\line(1,-1){5}}
%\put(40,12){\line(-1,-1){5}} \put(40,12){\line(1,-1){5}}
%\put(45,7){\line(-3,-5){3}} \put(45,7){\line(3,-5){3}}
%\put(10,17){\dashbox{1}(90,0){}} \put(10,12){\dashbox{1}(90,0){}}
%\put(10,7){\dashbox{1}(90,0){}} \put(10,2){\dashbox{1}(90,0){}}

%\put(1,17){\makebox{\tiny $\mathbb{R}\times \{0\}$}}
%\put(1,12){\makebox{\tiny $\mathbb{R}\times \{1\}$}}
%\put(1,7){\makebox{\tiny $\mathbb{R}\times \{2\}$}}
%\put(1,2){\makebox{\tiny $\mathbb{R}\times \{3\}$}}


\put(70, 17){\circle*{1}    \makebox{$u$}}  \put(85,17){\circle*{1} \makebox{$v$}}
\put(65,12){\circle*{1}} \put(75,12){\circle*{1}}
\put(80,12){\circle*{1}} \put(90,12){\circle*{1}}
\put(93,7){\circle*{1}} \put(87,7){\circle*{1}}
\put(83,7){\circle*{1}} \put(77,7){\circle*{1}}

\put(70,17){\line(1,0){15}} \put(70,17){\line(-1,-1){5}}
\put(70,17){\line(1,-1){5}} \put(85,17){\line(-1,-1){5}}
\put(85,17){\line(1,-1){5}} \put(90,12){\line(-3,-5){3}}
\put(90,12){\line(3,-5){3}} \put(80,12){\line(-3,-5){3}}
\put(80,12){\line(3,-5){3}}
\end{picture}
\caption{A good binary tree resulting after the deletion of 2 pairs of second neighbors of $u$.}
   \label{f3}
\end{figure}

It has been known that among trees with given number of vertices, the path maximizes and the 
star  minimizes the Wiener index, see \cite{ejs} or \cite{lovasz} Ex. 6.23. Regarding binary trees 
with given number of vertices,  the {\em caterpillar tree} maximizes the Wiener index \cite{rauten}, while
the {\em good tree} minimizes  the Wiener index \cite{rauten, sorder}.   \cite{degreeseq, zhang2008}
generalized the concept of {\em good trees} to {\em greedy trees} and proved that greedy trees 
minimize the Wiener index among trees with a given degree sequence. Among trees with a given degree sequence, finding the specific caterpillar that maximizes the Wiener index turned out to be difficult \cite{cela, zhang2010}. 

In   \cite{lepovic1998collective}, Lepovi\'c and Gutman conjectured
 that every positive integer, with only 49 explicit exceptions, is the 
Wiener index of some tree. This conjecture was verified independently 
in \cite{wagner2006class} and \cite{fortynine},  and further extended 
to the class of trees with maximum degree $3$ in \cite{wagner2008molecular}. This problem has some relevance to designing molecules with prescribed properties.

\subsection{Results for subtrees of trees}
In a bioinformatics paper, 
Knudsen \cite{dan} provided a multiple parsimony alignment algorithm, given  an affine gap cost
 and  a
phylogenetic tree. In bounding the time complexity of his algorithm, a
factor was the number of so-called ``acceptable residue configurations'',
which is the number of subtrees  of the phylogenetic tree containing at least one original
leaf vertex. Knudsen estimated the maximum
number of acceptable residue configurations
among all binary trees.  Let $F(T)$ denote the number of subtrees of the tree $T$  (a subtree must have at least one vertex), and let 
$F_T(v)$ denote the number of subtrees of the tree $T$ that contain vertex $v$.

Knudsen's work motivated our earlier papers \cite{subtrees, largest} to show the following results:
among all trees with a given number of vertices, the {\em path} minimizes the number of subtrees,
and the {\em star} maximizes the number of subtrees.  Furthermore, among binary trees 
with a given number of vertices, the {\em caterpillar} minimizes the number of subtrees, and the 
{\em good tree} maximizes the number of subtrees. (We also solved exactly Knudsen's original problem,
namely which binary tree maximizes the number of subtrees with at least one original leaf 
\cite{congnum}.) For trees with a given degree sequence, the  number of subtrees analogue of the Wiener index  result  for greedy trees was shown in \cite{gray}.  %\mnote{Grammar changed}

\cite{czabarkawagner} showed that the ``number of subtrees'' parameter also realizes  all positive integers,  except 34 explicitly
given numbers. The proof is
somewhat number theoretic as uses representation of integers as 
sum of pentagonal numbers.

\subsection{How far the analogy goes?}
The dual behaviour of the Wiener index and the number of subtrees, shown above, is just statistical,
not deterministic. 
Wagner \cite{correl} made an % careful
   analysis of the correlation between a number of pairs of tree indices, and
   he found the highest (negative) correlation between the Wiener index and the number of subtrees
   among the indices that he considered.
 

Recently  Taoyang Wu and us  \cite{taoyang} 
%reached a much better understanding and
 found a substantial
simplification and unification of the  results  in  \cite{subtrees}, \cite{congnum}, \cite{largest},
regarding   minimization of the Wiener index or maximization of the 
number of subtrees over certain families of trees, through the ``semi-regular property". 
Making use of this general property, the extremality of the greedy tree with respect to general distance-based graph invariants are shown recently \cite{nina}.
 Surprisingly, the motivation for a fruitful different view came from phylogenetics, where a quantity similar to the Wiener
index appeared, namely the sum of interleaf distances. 

It is worthwhile to investigate how far the dual behaviour goes as the papers \cite{subtrees} and \cite{largest} generated considerable 
    interest in different disciplines %and were cited by
     \cite{rulebased, hardness, hamina, hamina2, maxmatchings, indepsubsets, prodinger, hardness2, shuchao, shuchao2, maunz, speedup, self-similar,    correl,  yanyeh}. The analogy certainly goes
     one step further, to describe the ``middle part" of the tree.








\subsection{The centroid, center, and subtree core of a tree}
\label{core}
\bigskip
Much research has been devoted to define the ``middle part'' of a
tree. The first such result is due to Jordan \cite{jordan}. In a
tree $T$,  the {\em branch weight} of a vertex $v$, $bw(v)$, is
the maximum  number of edges over all subtrees of $T$ which
contain $v$ as a leaf. By definition, the {\em centroid} $C(T)$ of
$T$ is the set of vertices minimizing the branch weight. Jordan
\cite{jordan} showed that either $C(T)=\{c\}$, and $bw(c)\leq
\frac{n-1}{2}$ (we always denote the order of the tree by $n$), or $C(T)=\{c_1,c_2\}$, where $c_1$ and $c_2$ are
adjacent vertices with $bw(c_1)=bw(c_2)=\frac{n-1}{2}$, and in both
cases all other vertices have branch weight strictly exceeding
$\frac{n}{ 2}$. Zelinka \cite{zelinka} gave an alternative
characterization of the centroid: $C(T)$ contains exactly those
vertices $u$ of $V(T)$,  which {\em minimize} the distance function of
vertices, i.e. $\sigma_T(u)=\sum_{v\in V(T)} d_T(u,v)$.

Jordan \cite{jordan} also defined the  {\em center} of a tree $T$,
as the set of vertices minimizing the function {\em eccentricity}
$ecc(u)=\max_{v\in V(T)} d_T(u,v)$, and showed that the center contains
one vertex or two adjacent vertices. (For a contemporary reference, see
\cite{lovasz} 6.21 and 6.22.) \'Ad\'am \cite{adam} studied further concepts of
centrality in trees.

We defined the ``middle part'' of a tree in a new way in \cite{subtrees}:
 the {\em subtree core} of $T$, $Core (T)$, is the set of vertices
maximizing $F_T(v)$, number of subtrees of $T$ that contain $v$. We showed that 
the subtree core of any tree $T$ contains one or two vertices, and if the
subtree core contains two vertices, then they must be adjacent.
The ultimate reason for this phenomenon is that $F_T(.):V(T)\rightarrow \mathbb{R}$ is strictly concave along any path of $T$,
and hence $F_{T}$ is maximized at a single vertex or two adjacent
vertices on any path of $T$.
This new concept differs from the concept
of center and centroid. 


%First we
% are going to show  that $f_{T}$ is strictly concave along any path of $T$,
%and hence $f_{T}$ is maximized at a single vertex or two adjacent
%vertices on any path of $T$.



\section{The results}
   Barefoot, Entringer and Sz\'ekely \cite{barefoot} determined extremal values of
 $\sigma_T(w)/\sigma_T(u)$,   $\sigma_T(w)/\sigma_T(v)$, $\sigma(T)/\sigma_T(v)$,
       and $\sigma(T)/\sigma_T(w)$, 
where $T$ is a tree on $n$ vertices, $v$ is in the centroid $C(T)$
   of the tree $T$, and $u,w\in L(T) $ are leaves in $T$. (We use the notation $L(T)$ for the set of leaves
   of the tree $T$.)
   
   In this paper  we  test how far the negative correlation between
   distances and subtrees go if we look for the   extremal values
   of $F_T(w)/F_T(u)$, $F_T(w)/F_T(v)$, $F(T)/F_T(v)$,  
   and $F(T)/F_T(w)$, where $T$ is a tree on $n$ vertices, $v$ is in the subtree core
   of the tree $T$, and $u,w$ are leaves in $T$---the complete analogue of  \cite{barefoot}, 
    changing distances to the number of subtrees.  
    Note that extremal behaviour of {\em fractions}
   is always more delicate than that of the numerator and denominator, therefore it is a natural step
   to see how far duality between Wiener index and the number of subtrees extend when we study
   extreme values of the ratios above. 
     Comparison of extremal trees is particularly interesting. The Table summarizes our results.


From the two columns of ``extremal tree'', it is easy to see the correspondence between trees maximizing (minimizing) the distance function and the ones minimizing (maximizing) the subtree function. In rows 1, 3 and 6 of the table, the extremal trees are comets. The different path length
is explained by the distance of a vertex always being polynomial in $n$, while the  number of
subtrees containing a vertex being typically exponentially large.  The star is extremal in
row 5. In row 2, the extremal tree is a path with an added vertex---but added at a different place.
Rows 4 and 7 show different extremal trees for the two problems---still, the dumbbell contains a
long path, while the other extremal tree is a path, and the spider has a central vertex like a star.

Theorems~\ref{rat3.2} and \ref{rat2.3} seem to have the same $r$-comet as extremal tree, as we have 
to round almost the same number to obtain $r$.
However, in neither of the two results we know when to round up or down, so the extremal $r$'s 
may differ. In Theorem~\ref{vs3.3}, the quantity to be rounded to obtain $r$ for the comet, is bigger
by one than in the cited two theorems.

\noindent
\newpage
%\begin{rotate}{270}
\Large
\begin{sidewaystable} \begin{center}
\scalebox{0.9}{
%\begin{table}
\begin{tabular}% \label{first}
{| l | c | c|c |c| c|}
\hline Distance problem
 & Bound &Extremal tree &     Subtree problem & Bound & Extremal tree\\
\hline
$\displaystyle\frac{\sigma_T(w)}{\sigma_T(u)}:u,w\in L(T)\atop \hbox{maximize}$&   ${\leq \atop \sim}\frac{\sqrt{n}}{2}$& $\hbox{$r$-comet, $r\approx 2\sqrt{n}$} \atop \hbox{\cite{barefoot} Thm. 2}$ & $\displaystyle\frac{F_T(w)}{F_T(u)}:u,w\in L(T)\atop 
\hbox{maximize}$ &${\geq\atop \sim} \frac{n}{2} $&
$\hbox{$r$-comet, $r\approx n-2\log_2 n$}\atop \hbox{ Thm. \ref{rat3.2}}$\\
%$\hbox{$r$-comet, $r\approx 2\sqrt{n}$} \atop \hbox{\cite{barefoot} Thm. 2}$\\
\hline 
$\displaystyle\frac{\sigma_T(w)}{\sigma_T(v)}:{w\in L(T),\atop v\in C(T)}\atop \hbox{minimize}  $& ${\geq \atop \sim } 1$&  ${\hbox{path with a leaf added}\atop \hbox{  at middlepoint }}\atop \hbox{\cite{barefoot} Thm. 3}$ & $\displaystyle\frac{F_T(w)}{F_T(v)}:{w\in L(T),
\atop v\in Core(T)}\atop \hbox{maximize} $&${\leq\atop \sim} 2$& ${\hbox{  path with a leaf added}\atop \hbox{  at position $\approx 2n/3$ } } \atop \hbox{ Thm. \ref{rat4.6}}$
\\
\hline 
$\displaystyle\frac{\sigma_T(w)}{\sigma_T(v)}:{w\in L(T), \atop v\in C(T) } \atop \hbox{maximize} $
  & ${\leq \atop \sim} \sqrt{\frac{n}{2}} $& $\hbox{$r$-comet, $r\approx \sqrt{2n}$}\atop \hbox{\cite{barefoot} Thm. 3}$ & $\displaystyle\frac{F_T(w)}{F_T(v)}:{w\in L(T),\atop v\in Core(T)}\atop \hbox{minimize}$ & ${\geq\atop \sim} n $& $\hbox{$r$-comet, $r\approx n-2\log_2 n$}\atop \hbox{ Thm. \ref{rat2.3}}$  \\
\hline 
$\displaystyle \frac{\sigma_T}{\sigma_T(v)}:v\in C(T)  \atop \hbox{minimize} $  & ${\geq \atop \sim } \frac{n}{2}$&$\hbox{  $r$-dumbbell, $r\approx 2\sqrt{n}$}\atop \hbox{\cite{barefoot} Thm. 4}$ & $\displaystyle\frac{F_T}{F_T(v)}: v\in Core(T) \atop \hbox{maximize} $ & 
%$  \leq \begin{cases}
%\frac{2n}{n+1}, & \hbox{if }  n \hbox{ odd }\cr
%\frac{2n+2}{n+2}, & \hbox{if }  n \hbox{ even }\end{cases}$
$\leq 1+\frac{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{n}{2}\rfloor+1  }$
&$\hbox{  path }\atop \hbox{Thm. 
 \ref{vs4.4}, proof in \cite{sibling}}$ \\
\hline
$\displaystyle \frac{\sigma_T}{\sigma_T(v)}:v\in C(T)  \atop \hbox{maximize}  $ & $\leq n-1$ &$\hbox{ star } \atop \hbox{\cite{barefoot} Thm. 4}$  & $\displaystyle\frac{F_T}{F_T(v)}: v\in Core(T)\atop \hbox{minimize}$&  $\geq 1+\frac{n-1}{2^{n-1}}$&
$\hbox{  star }\atop \hbox{Thm. \ref{vs2.2}, proof in \cite{sibling}}$  \\
\hline
$\displaystyle \frac{\sigma_T}{\sigma_T(w)}:w\in L(T)  \atop \hbox{minimize}  $  &  ${\geq \atop \sim } \sqrt{2n}$&  $\hbox{   $r$-comet, $r\approx \sqrt{n}$} \atop \hbox{\cite{barefoot} Thm. 5}$ & $\displaystyle \frac{F_T}{F_T(w)}:w\in L(T)  \atop \hbox{maximize}  $ &${\leq\atop \sim} n$&
$\hbox{$r$-comet, $r\approx n-2\log_2 n$        } \atop\hbox{ Thm. \ref{vs3.3}, proof in \cite{sibling}}$\\
\hline
$\displaystyle \frac{\sigma_T}{\sigma_T(w)}:w\in L(T) \atop \hbox{maximize}   $  &${\leq \atop \sim } n$& $\hbox{spider } \atop\hbox{\cite{barefoot} Thm. 5}$& 
$\displaystyle \frac{F_T}{F_T(w)}:w\in L(T) \atop \hbox{minimize}    $ &$\geq \frac{2^{n-1}+n-1}{1+2^{n-2}}$&
$\hbox{   star } \atop \hbox{Thm. \ref{vs2.3}, proof in \cite{sibling}}$\\
\hline
\end{tabular}
}
\caption{Comparison of results. \newline %To explain the terminology in  the Table, 
An {\em $r$-comet} is an $n$-vertex tree made of an $r$-path with $n-r$ leaves 
joined to its left endpoint. \newline An {\em $r$-dumbbell} is an  $r$-path with equal number of leaves joined to its endpoints
to make an $n$-vertex tree. \newline A {\em spider} is an $n$-vertex tree, which
 has a special vertex $v$,
has a single leaf joined to $v$, and has the \newline remaining $n-2$ vertices distributed  on $\lceil  \sqrt{3n}  \rceil$    paths, whose length can differ by at most 1,  and all start from $v$. 
\newline The notation $r\approx g(n)$  means that the  extremal tree occurs
for an $r$ value, such that $r-g(n)$
remains bounded as $n\rightarrow \infty$. \newline
(\cite{barefoot} and our results are more specific about the value of $r$, but  it is inconvenient to show in a succinct table.) 
\newline In the {\em Bound} columns  ${\leq \atop \sim} f(n)$  means that an inequality is
valid for  a quantity that is asymptotically equal to  $f(n)$  as $n\rightarrow \infty$.
\newline Some of the results for distances  require that $n$ is sufficiently large. 
\newline The problem in the first row is not given a 
minimization version, as upper and lower bounds are reciprocals of each other.
}
%\end{table}
\end{center}
\end{sidewaystable}
\normalsize

%\bigskip\bigskip\bigskip\bigskip

%\end{rotate}
\clearpage
%\normalsize
 
%$$R(t)= \max_{w,u \in L(T)} \left\{ \frac{F_T(w)}{F_T(u)} \right\}. $$
\begin{theorem} \label{rat3.2}
Among trees $T$ of order $n$, the maximum value of $ \max_{w,u \in L(T)} \left\{ \frac{F_T(w)}{F_T(u)} \right\}  $ is achieved by a tree $T$ formed from identifying the center of the star $K_{1,x}$ with one end vertex   of the path $P_{n-x}$,
and only by such trees. 
\end{theorem}

For trees of this description the value   $\frac{F_T(w)}{F_T(u)} $ can be explicitly formulated as a function of $x$: $$ f(x):=\frac{1+(n-x) 2^{x-1}}{n-x-1 + 2^{x}}.$$

Trying to maximize $f(x)$ for real $x$'s,  from  $f'(x)=0$  we observe 
\begin{equation}\label{eq:solve2}
(n-x)(n-x-1)2^{x-1} \ln 2 + 1 + 2^{x-1} = 2^{2x-1} + 2^x \ln 2.
\end{equation}
%The solution of $x$ to \eqref{eq:solve2} will provide us the structure of the tree that maximizes $R(T)$ with $|V(T)|=n$.
Although the asymptotic calculations using iteration are routine, we show the details in this
instance and skip the details later.
Using the substitution $x\leftarrow n-y$, (\ref{eq:solve2}) can be rewritten as
$$2^y\Bigl(y(y-1)\ln 2 +1 + 2^{1+y-n} -2\ln 2\Bigl)=2^n.$$
As the left-hand side is an increasing function of $y$, it has a unique $y_0(n)$ solution for every 
positive integer $n$. Taking logarithm of both sides,
$$y_0(n)+ \log_2 \Bigl(y_0(n)(y_0(n)-1)\ln 2 +1 + 2^{1+y_0(n) -n} -2\ln 2\Bigl)=n.$$
Substituting $y_0(n)\leftarrow n-  \log_2 \Bigl(y_0(n)(y_0(n)-1)\ln 2 +1 + 2^{1+y_0(n) -n} -2\ln 2\Bigl) $ in the previous equation
for the occurrences of $y$ in the logarithmic term, we obtain
$$y_0(n)+2\log_2 n +\frac{\ln\ln 2}{\ln 2}+o(1)=n$$
and from here the $x_0(n)$ solution to  (\ref{eq:solve2}) is
$$x_0(n)=2\log_2 n +\frac{\ln\ln 2}{\ln 2}+o(1).$$
Hence, in the Table, $r=\lfloor y_0(n)\rfloor $ or   $r=\lceil y_0(n)\rceil $.
It is easy to see that $f(\lfloor x_0(n)\rfloor 
)\sim f(\lceil x_0(n)\rceil    ) \sim \frac{n}{2}$.

\vskip0.5cm

The following two theorems find extreme values of the {\em reciprocals} of the quantities in the second 
and third lines of the table:



\begin{theorem} \label{rat2.3}
Among trees $T$ of order $n$,
the maximum value of $\max_{v\in Core(T), u\in L(T)} \left\{ \frac{F_T(v)}{F_T(u)} \right\} $
 is achieved by a tree $T$ formed from identifying the center $v$ of the star $K_{1,x-1}$ with one end vertex of the path $P_{n-x+1}$ such that $v \in Core(T)$, and only by such trees.  \end{theorem}

For trees of this description the value   $\frac{F_T(v)}{F_T(u)} $ can be explicitly formulated as a function of $x$:
$$ f(x):=\frac{(n-x+1) 2^{x-1}}{n-x + 2^{x-1}}. $$
Trying to maximize $f(x)$ for real $x$'s, observe 
%Now setting
%\begin{align*}
 %& 
$$ f'(x)
= \frac{ (n-x+2^{x-1} ) \left( -2^{x-1} + (n-x+1)2^{x-1} \ln 2 \right) - (n-x+1) 2^{x-1} (-1 + 2^{x-1} \ln 2) }
{(n-x + 2^{x-1})^2},$$
and that the solutions of $f'(x)=0$ are exactly the solutions of
% \\
%=& 0
%\end{align*}
%yields
\begin{equation}\label{eq:solve1}
(\ln 2) (n-x) (n-x+1) = 2^{x-1} - 1. 
\end{equation}
It is easy to see that there is only one solution $x_0(n)$ to (\ref{eq:solve1}), and 
standard asymptotic calculations show that 
$$n-x_0(n)+1=n-2 \log_2 n -\frac{\ln \ln 2}{\ln 2} +o(1).$$
Hence, in the Table, $r=n+1-\lfloor x_0(n)\rfloor $ or   $r=n+1-\lceil x_0(n)\rceil $.
It is easy to see that $f(\lfloor x_0(n)\rfloor 
)\sim f(\lceil x_0(n)\rceil    ) \sim n$.




%-------------------------------------

\begin{theorem} \label{rat4.6}
Among trees of order $n\geq 5$, $\min_{v\in Core(T), u\in L(T)} \left\{ \frac{F_T(v)}{F_T(u)}\right\}$  is achieved if and only if $T$ is formed from attaching one pendant vertex $u$ to $v=v_x$ of a path $v_0v_1v_2\ldots v_{n-2}$. Here
$$ x = \left\lfloor \frac23  (n - 1) \right\rfloor.$$
\end{theorem}
%$v=v_x$, $u=z$ and
The minimum value of $\frac{F_T(v)}{F_T(u)}$ is 
$$ \frac{ 2 (n - x - 1)(x+1) }{1 + (n - x - 1)(x+1)}, $$
which is asymptotically equal to 2.





%-------------------------------------------------------------
The following 4 theorems are proved in a sibling paper  \cite{sibling}, to keep the length of this paper under control: 


\begin{theorem}   \label{vs2.2} %\label{theo:star2}
Among trees of order $n$ with  $v \in Core(T)$,
$$ \frac{F(T)}{F_T(v)} \geq 1 + \frac{n-1}{2^{n-1}} $$
with equality if and only if $T$ is a star centered at $v$.
\end{theorem}


%---------------------------------


\begin{theorem} \label{vs4.4}
Among trees $T$ of order $n$, where  $v\in Core(T)$, the maximum value of $\frac{F(T)}{F_T(v)}$ is obtained by a path, with
$$ \frac{F(T)}{F_T(v)}=1+\frac{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{n}{2}\rfloor+1  }.$$
%if $n$ is odd and
%$$ \frac{F(T)}{F_T(v)}=1+\frac{n}{n+2}$$
%if $n$ is even.
\end{theorem}


%-------------------------------

\begin{theorem}   \label{vs2.3}         %\label{theo:star2}
Among trees $T$ of order $n$, where $u \in L(T)$,
$$ \frac{F(T)}{F_T(u)} \geq \frac{2^{n-1} + n - 1}{1+2^{n-2}} $$
with equality if and only if $T$ is a star.
\end{theorem}

%--------------------------

\begin{theorem} \label{vs3.3}
Among trees $T$ of order $n$,  $ \max_{u\in L(T)}\left\{\frac{F(T)}{F_T(u)}\right\}$ is achieved when $T$ is an $(x+1)$-comet and
$u$ is a leaf that has a degree 2 neighbor, and only by such trees.
\end{theorem} % path of length $x$, 
%whose other end is identified with the center of a star on $n-x$ vertices. 
For trees of this description the value   $\frac{F(T)}{F_T(u)} $ can be explicitly formulated as a function of $x$:
$$ f(x):  = \frac{ 2^{n-x-1}(x+1) + \frac12 x(x-1) + (n-1) } {2^{n-x-1} + x}. $$

The function $f(x)$ is maximized when $x=n - 2 \log_2 n - \frac{\ln \ln 2}{\ln 2} + o(1)$. This complicated analysis is detailed in \cite{sibling}.

\section{Open problems}
After having understood many extremal properties of the number of subtrees, next one would
like to understand how they relate to global properties.
\begin{problem} Does the multiset $\{F_T(v): v\in V(T)\}$ determine the tree $T$?
\end{problem}
It makes sense to look for a more refined information than $F_T(v)$: let $F_T(v,x)$ denote the
the number of subtrees of $T$ {\em of order $x$} that contain vertex $v$. Also, instead of an
underlying tree $T$, we may
consider a {\em graph} $G$.
There are results on computing the number of subtrees of trees with dynamic programming \cite{yanyeh}.
\begin{problem} Are there determinant formulae to compute     $F_T$, $F_T(v)$,  $F_T(v,x)$?
Or even more general, $F_G$, $F_G(v)$,  $F_G(v,x)$? Is there a way to {\em approximate} these
numbers in a very large graph efficiently?
\end{problem}
\begin{problem} Are the distributions  $F_G(v,x):  x\in \NN$  $(v\in V(G))$ connected to connectivity, expansion, or spectral properties of the underlying graph $G$?
\end{problem}
The following problem is somewhat vague:
\begin{problem} Given two graphs, $G_1$ and $G_2$, not necessarily of the same order or size,
can we conclude from the ``similarity" of  the distributions $F_{G_i}(v,x):  x\in \NN$ $(v\in V(G_i))$ the
``similarity" of $G_1$ and $G_2$?
   \end{problem}


%INSERT
\section{Proof to Theorem~\ref{rat2.3} }%Upper bound of $\frac{F_T(v)}{F_T(u)}$}
\label{sec:max_vu}

Given a tree $T$ of order $n$,  we want to find the maximum of 
$$ R(T):= \max_{v\in Core(T), u\in L(T)} \left\{ \frac{F_T(v)}{F_T(u)} \right\}.$$
First note $u=v$ is only possible in $\leq 2$-vertex trees---by the strict concavity of $F_T(.)$ along paths, mentioned in Section~\ref{core}. 

%We first show that the maximum value of $R(T)$ can only be obtained by a tree $T$ where  Namely the following:

\begin{lemma}\label{lem:max_vu}
If $v \in Core(T)$ and $u \in L(T)$, and $R(T)$ is maximized by  $\frac{F_T(v)}{F_T(u)}$ among trees of order $n$, then
the 
internal vertices of the path connecting $v$ and $u$ have  degree 2. 
%In the tree $T$ that obtains the maximum $R(T)$ is formed by a tree rooted at $v$ (say $T_v$) with a path from $u$ to $v$ (denoted by $P_{u,v}$) attached 
(See Fig.~\ref{fig:max_vu}, we denote the $uv$ path by $P_{u,v}$). %Here.
\end{lemma}

\begin{figure}[htbp]
\centering
    \begin{tikzpicture}[scale=1]
        \node[fill=black,circle,inner sep=1pt] (t0) at (0,0) {};
        \node[fill=black,circle,inner sep=1pt] (t1) at (1,0) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,0) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,0) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,0) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,0) {};
        
        \draw (t0)--(t1);
        \draw (t1)--(t2);
        \draw [style=dashed] (t2)--(t3);
        \draw (t3)--(t4);
        \draw (t4)--(t5);
        
        \draw (5,0)--(5.5,-1)--(4.5,-1) -- cycle;
        
        \node at (5,-.8) {$T_v$};
        \node at (5,.2) {$v$};
        \node at (0,.2) {$u$};
        
        
     \end{tikzpicture}
\caption{$T_v$ and $P_{u,v}$.}\label{fig:max_vu}
\end{figure}

\begin{proof}
%Let $T, v, u$ obtain $R(T)$ and 
List the vertices of the $P_{u,v}$ path as $P_{u,v}:=uv_1v_2 \ldots v_k v$, and assume $k\geq 1$, otherwise we have nothing to prove.
% be the path connecting $u$ and $v$. 
 Let $A_0=\{u\}, A_1, A_2, \ldots, A_k, A_{k+1}=T_v $ denote the connected components (trees) in $T-E(P_{u,v})$, with $v_i \in A_i$ for $1\leq i \leq k$ and $v \in T_v$. 

Suppose (for contradiction) that $A_i$ is not a single vertex for some $1\leq i \leq k$,  and consider a tree $T'$ obtained by moving all $A_i $'s  from $v_i$  to $v$ (see Fig.~\ref{fig:lem_max_vu}). 

\begin{figure}[htbp]
\centering
    \begin{tikzpicture}[scale=1.5]
        \node[fill=black,circle,inner sep=1pt] (t0) at (0,0) {};
        \node[fill=black,circle,inner sep=1pt] (t1) at (1,0) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,0) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,0) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,0) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,0) {};
        
        \draw (t0)--(t1);
        \draw (t1)--(t2);
        \draw [style=dashed] (t2)--(t3);
        \draw (t3)--(t4);
        \draw (t4)--(t5);
        
        \draw (5,0)--(5.3,-1)--(4.7,-1) -- cycle;
        \draw (4,0)--(4.3,-1)--(3.7,-1) -- cycle;
        \draw (3,0)--(3.3,-1)--(2.7,-1) -- cycle;
        \draw (2,0)--(2.3,-1)--(1.7,-1) -- cycle;
        \draw (1,0)--(1.3,-1)--(0.7,-1) -- cycle;

        \node at (5,-.8) {$T_v$};
        \node at (5,.2) {$v$};
        \node at (4,-.8) {$A_k$};
        \node at (4,.2) {$v_k$};
        \node at (3,-.8) {$A_{k-1}$};
        \node at (3,.2) {$v_{k-1}$};
        \node at (2,-.8) {$A_2$};
        \node at (2,.2) {$v_2$};
        \node at (1,-.8) {$A_1$};
        \node at (1,.2) {$v_1$};
        \node at (0,.2) {$u$};
        
        \node at (-.7,-.5) {{\huge $T:$}};
        
        
        
        
        \node[fill=black,circle,inner sep=1pt] (t0) at (0,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t1) at (1,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,-3) {};
        
        \draw (t0)--(t1);
        \draw (t1)--(t2);
        \draw [style=dashed] (t2)--(t3);
        \draw (t3)--(t4);
        \draw (t4)--(t5);
        
        \draw (5,-3)--(5.3,-4)--(4.7,-4) -- cycle;
        \draw (5,-3)--(5.45,-3.85)--(5.9,-3.4) -- cycle;
        \draw (5,-3)--(5.45,-2.15)--(5.9,-2.6) -- cycle;
        \draw [line width=0.3mm] [style=dotted] (5.7, -2.8)--(5.7, -3.2);
        

        \node at (5,-3.8) {$T_v$};
        \node at (5,-2.8) {$v$};
        \node at (5.5,-2.55) {$A_k$};
        \node at (4,-2.8) {$v_k$};
        \node at (3,-2.8) {$v_{k-1}$};
        \node at (2,-2.8) {$v_2$};
        \node at (5.5,-3.45) {$A_1$};
        \node at (1,-2.8) {$v_1$};
        \node at (0,-2.8) {$u$};
        
        \node at (-.7,-3.5) {{\huge $T':$}};
        
     \end{tikzpicture}
\caption{Making $T'$ from $T$.}\label{fig:lem_max_vu}
\end{figure}

Simple enumerations give the following Horner's scheme like formulae:
$$ F_T(u) = \Biggl( \ldots \biggl(\Bigl((F_{T_v}(v) + 1 )F_{A_k}(v_k)+ 1\Bigl)F_{A_{k-1}}(v_{k-1}) + 1\biggl) \ldots +1\Biggl)F_{A_1}(v_1) + 1 ; $$
\begin{equation}
\label{eq:comp1}
F_{T'}(u) = k+1+F_{T_v}(v) \prod_{i=1}^k F_{A_i}(v_i) < F_T(u); 
\end{equation}
and
$$ F_T(v) = F_{T_v}(v) \Biggl( 1 + F_{A_k}(v_k)\biggl( 1 + F_{A_{k-1}}(v_{k-1}) \Bigl(1+ \ldots (1+ 2F_{A_1}(v_1)  ) \ldots \Bigl)\biggl)\Biggl) ; $$
\begin{equation}
\label{eq:comp2}
F_{T'}(v) = (k+2) F_{T_v}(v) \prod_{i=1}^k F_{A_i}(v_i) > F_T(v),
\end{equation}
unless $F_{A_i}(v_i)=1$ for all $1\leq i\leq k$, which is equivalent to $v_i$ having degree 2 in $T$.

Intuitively, \eqref{eq:comp1} and \eqref{eq:comp2} can be understood as moving any ``branch'' away from $u$ and closer to $v$ will decrease the number of subtrees containing $u$ and increase that of $v$. 
Hence by \eqref{eq:comp1} and \eqref{eq:comp2}, we have
$$ R(T') \geq \frac{F_{T'}(v)}{F_{T'}(u)} > \frac{F_T(v)}{F_T(u)}, $$
a contradiction.
\end{proof}

Assuming   $|V(T_v)|=x$, knowing  that the tree has order 
 $n$, we obtain  $|V(P_{u,v})|=n-x+1$. We can get explicitly 
$$ F_T(u) = n-x + F_{T_v}(v) $$
and
$$ F_T(v) = (n-x+1) \cdot F_{T_v}(v). $$
Therefore 
\begin{equation}\label{eq:R1}
\frac{F_T(u)}{F_T(v)} = \frac{1}{n-x+1} + \frac{n-x}{n-x+1} \cdot \frac{1}{F_{T_v}(v)}.
\end{equation}
Hence, for given $n$ and $x$, $\frac{F_T(v)}{F_T(u)}$ is maximized if and only if \eqref{eq:R1} is minimized, which is the case if and only if $F_{T_v}(v)$ is maximized. The following simple observation will be used.

\begin{lemma}\label{lem:T_v_star}
Given $x=|V(T_v)|$, 
$$F_{T_v}(v) \leq 2^{x-1} $$ 
with equality if and only if $T_v$ is a star centered at $v$.
\end{lemma}

\begin{proof}
This is trivial by noting that any subtree of $T_v$ containing $v$ induces a unique subset of $V(T_v)\setminus \{v\}$. Hence the total number of such subtrees is at most the number of such subsets.
\end{proof}

%\begin{rem}
It is easy to see that, by changing $T_v$ to be a star centered at $v$ to maximize $F_{T_v}(v)$, $v$ stays in the subtree core of $T$.
%\end{rem}
Thus we proved Theorem~\ref{rat2.3}.

\section{Proof to Theorem~\ref{rat3.2}}%Bound of $\frac{F_T(w)}{F_T(u)}$}
\label{sec:max_wu}

Essentially the  approach of the previous  Section~\ref{sec:max_vu} will handle this question, so we skip some of the details. 
Given a tree $T$ of order $n$,  we want to find the maximum of 
$$ R(T) =\max_{w,u \in L(T)} \left\{ \frac{F_T(w)}{F_T(u)} \right\}. $$
First note $uw\in E(T)$ is only possible in $ 2$-vertex trees. Choosing $w=u$ provides in any
tree $R(T)=1$, as is the case of $d_T(w,u)=2$.  Below we construct trees and leaves with higher ratios.  For an optimal tree $T$ 
and leaves $u,w$,
let the path connecting $w$ and $u$ be $P_{w,u} = u v_1 v_2 \ldots v_k w$, and by the arguments 
above we can assume $k>1$.  Let $A_i$ be  defined as in Section~\ref{sec:max_vu}   for $1\leq i \leq k$. Like in the proof of Lemma~\ref{lem:max_vu}, by moving all $A_i'$s for $1\leq i \leq k-1$ to $v_k$ we obtain $T'$ with
$$ \frac{F_{T'}(w)}{F_{T'}(u)} > \frac{F_T(w)}{F_T(u)},$$
unless $F_{A_i}(v_i)=1$ for all $1\leq i\leq k$, which is equivalent to $v_i$ having degree 2 in $T$.
See Fig.~\ref{fig:lem_max_wu} for illustration.
Indeed,
$$ F_T(u) = \Biggl( \ldots \biggl(\Bigl(2F_{A_k}(v_k)+ 1\Bigl)F_{A_{k-1}}(v_{k-1}) + 1\biggl) \ldots +1\Biggl)F_{A_1}(v_1) + 1 ; $$
\begin{equation}
\label{eq:comp1*}
F_{T'}(u) = k+2 \prod_{i=1}^k F_{A_i}(v_k) < F_T(u); 
\end{equation}
and
$$ F_T(w) = \Biggl( \ldots \biggl(\Bigl(2F_{A_1}(v_1)+ 1\Bigl)F_{A_{2}}(v_{2}) + 1\biggl) \ldots +1\Biggl)F_{A_k}(v_k) + 1 ; $$

\begin{equation}
\label{eq:comp2*}
F_{T'}(w) = 1+(k+1)  \prod_{i=1}^k F_{A_i}(v_k) > F_T(w),
\end{equation}
unless $F_{A_i}(v_i)=1$ for all $1\leq i\leq k$, which is equivalent to $v_i$ having degree 2 in $T$.


 
\begin{figure}[htbp]
\centering
    \begin{tikzpicture}[scale=1.5]
        \node[fill=black,circle,inner sep=1pt] (t0) at (0,0) {};
        \node[fill=black,circle,inner sep=1pt] (t1) at (1,0) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,0) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,0) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,0) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,0) {};
        \node[fill=black,circle,inner sep=1pt] (t6) at (6,0) {};
        
        \draw (t0)--(t1);
        \draw (t1)--(t2);
        \draw [style=dashed] (t2)--(t3);
        \draw (t3)--(t4);
        \draw (t4)--(t5);
        \draw (t5)--(t6);
        
        \draw (5,0)--(5.3,-1)--(4.7,-1) -- cycle;
        \draw (4,0)--(4.3,-1)--(3.7,-1) -- cycle;
        \draw (3,0)--(3.3,-1)--(2.7,-1) -- cycle;
        \draw (2,0)--(2.3,-1)--(1.7,-1) -- cycle;
        \draw (1,0)--(1.3,-1)--(0.7,-1) -- cycle;

        \node at (6,.2) {$w$};
        \node at (5,-.8) {$A_k$};
        \node at (5,.2) {$v_k$};
        \node at (4,-.8) {$A_{k-1}$};
        \node at (4,.2) {$v_{k-1}$};
        \node at (3,-.8) {$A_{k-2}$};
        \node at (3,.2) {$v_{k-2}$};
        \node at (2,-.8) {$A_2$};
        \node at (2,.2) {$v_2$};
        \node at (1,-.8) {$A_1$};
        \node at (1,.2) {$v_1$};
        \node at (0,.2) {$u$};
        
        \node at (-.7,-.5) {{\huge $T:$}};
        
        
        
        
        \node[fill=black,circle,inner sep=1pt] (t0) at (0,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t1) at (1,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t6) at (6,-3) {};
        
        \draw (t0)--(t1);
        \draw (t1)--(t2);
        \draw [style=dashed] (t2)--(t3);
        \draw (t3)--(t4);
        \draw (t4)--(t5);
        \draw (t5)--(t6);
        
        \draw (5,-3)--(5.45,-3.85)--(5.9,-3.4) -- cycle;
        \draw (5,-3)--(4.55,-3.85)--(4.1,-3.4) -- cycle;
        \draw [line width=0.3mm] [style=dotted] (4.7, -3.7)--(5.3, -3.7);
        

        \node at (6,-2.8) {$w$};
        \node at (5,-2.8) {$v_k$};
        \node at (5.5,-3.45) {$A_k$};
        \node at (4,-2.8) {$v_{k-1}$};
        \node at (3,-2.8) {$v_{k-2}$};
        \node at (2,-2.8) {$v_2$};
        \node at (4.5,-3.45) {$A_1$};
        \node at (1,-2.8) {$v_1$};
        \node at (0,-2.8) {$u$};
        
        \node at (-.7,-3.5) {{\huge $T':$}};
        
     \end{tikzpicture}
\caption{$T'$ and $T$ with respect to $w$ and $u$.}\label{fig:lem_max_wu}
\end{figure}

Thus we have the following analogue of Lemma~\ref{lem:max_vu}.

\begin{lemma}
$R(T)$ is maximized by a tree $T$ and $w,u\in L(T)$ only if $T$ is formed by a tree $T_v$ rooted at $v$ with a path from $u$ to $v$ and an edge $wv$ (Fig.~\ref{fig:max_wu}).
\end{lemma}

\begin{figure}[htbp]
\centering
    \begin{tikzpicture}[scale=1]
        \node[fill=black,circle,inner sep=1pt] (t0) at (0,0) {};
        \node[fill=black,circle,inner sep=1pt] (t1) at (1,0) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,0) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,0) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,0) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,0) {};
        \node[fill=black,circle,inner sep=1pt] (t6) at (6,0) {};
        
        \draw (t0)--(t1);
        \draw (t1)--(t2);
        \draw [style=dashed] (t2)--(t3);
        \draw (t3)--(t4);
        \draw (t4)--(t5);
        \draw (t5)--(t6);
        
        \draw (5,0)--(5.5,-1)--(4.5,-1) -- cycle;
        
        \node at (5,-.8) {$T_v$};
        \node at (5,.2) {$v$};
        \node at (0,.2) {$u$};
        \node at (6,.2) {$w$};
        
     \end{tikzpicture}
\caption{$T_v$ and $P_{u,v}$ with respect to $w$ and $u$.}\label{fig:max_wu}
\end{figure}

Assume  $|V(T_v)|=x$, then $|V(P_{u,v})|=n-x$ as the tree $T$ has order $n$. It is easy to see
that 
$$ F_T(u) = n-x-1 + 2 F_{T_v}(v) = n-x-1 + 2\Bigl( F_{T_v}(v) + \frac{1}{n-x} \Bigl) - \frac{2}{n-x} $$
and
$$ F_T(w) = 1+ (n-x) \cdot F_{T_v}(v) = (n-x) \Bigl( \frac{1}{n-x} + F_{T_v}(v) \Bigl). $$
Therefore 
\begin{equation}\label{eq:max_wu}
\frac{F_T(u)}{F_T(w)} = \frac{2}{n-x} + \frac{n-x-1 - \frac{2}{n-x}}{n-x} \cdot \frac{1}{\frac{1}{n-x} + F_{T_v}(v)}.
\end{equation}
Hence, with given $n$ and $x$, $\frac{F_T(w)}{F_T(u)}$ is maximized if and only if \eqref{eq:max_wu} is minimized, which is the case when $F_{T_v}(v)$ is maximized.
Using Lemma~\ref{lem:T_v_star} again, we obtain Theorem~\ref{rat3.2}.



\section{Proof to Theorem~\ref{rat4.6}}%Lower bound of $\frac{F_T(v)}{F_T(u)}$}
\label{sec:min_vu}
Let 
$$ R(T) = \min_{v \in Core(T), u\in L(T)} \left\{ \frac{F_T(v)}{F_T(u)} \right\}.$$
%By, we can formally state the following important fact.
We need the following important Lemma, which will immediately follow from Lemmas~\ref{lem:min_vu1} and \ref{lem:min_vu2}:
\begin{lemma}\label{lem:min_vu3}
For $T$ with given $|V(T)|=n\geq 2$, $u \in L(T)$ and $v \in Core(T)$ that achieves the minimum value of $R(T)$, $u$ and $v$ must be adjacent (Fig.~\ref{fig:min_vu1}).
\end{lemma}
\begin{figure}[htbp]
\centering
    \begin{tikzpicture}[scale=1]
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,0) {};
        \node[fill=black,circle,inner sep=1pt] (t6) at (6,0) {};
        
        \draw (t5)--(t6);
        
        \draw (5,0)--(5.5,-1)--(4.5,-1) -- cycle;
        
        \node at (5,-.8) {$T_v$};
        \node at (5,.2) {$v$};
        \node at (6,.2) {$u$};
        
     \end{tikzpicture}
\caption{$uv \in E(T)$ to minimize $R(T)$.}\label{fig:min_vu1}
\end{figure}

%We will first show that the minimum value of $R(T)$, with given $|V(T)|=n$, is obtained when $uv \in E(T)$. 
Assume that $T$ is the tree that minimizes $R(T)$.  
As $n\geq 2$, there is a
 (unique) neighbor $x$ of $u$ in $T$. For contradiction, assume   $x\notin Core(T)$. Consider the tree  $T' $ obtained from $T$ by deleting the $ \{xu\}$ edge and adding the  $\{vu\}$ edge.
 We will establish  that $v \in Core(T')$ and $ \frac{F_{T'}(v)}{F_{T'}(u)} < \frac{F_T(v)}{F_T(u)} $ in the following two Lemmas, providing the contradiction.
\begin{lemma}\label{lem:min_vu1}
With $u\in L(T)$  and $v \in Core(T)$ and $T'$ defined as above, we must have
$$ v \in Core(T').$$
\end{lemma}
\begin{lemma}\label{lem:min_vu2}
If the unique neighbor $x$ of $u$ is not a subtree core vertex of $T$, then
$$ \frac{F_{T'}(v)}{F_{T'}(u)} < \frac{F_T(v)}{F_T(u)}. $$
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lem:min_vu1}]
Assume $n\geq 3$, otherwise we have nothing to prove. %Under this condition observe
%\begin{equation} \label{egylepes}
%F_{T'}(v)=2F_{T\setminus\{u\}}(v) >F_T(v).
%\end{equation}
%It follows that 
%\begin{equation} \label{ketlepes}
%F_{T'}(u)=1+\frac{F_{T'}(v)}{2} \leq F_{T'}(v).
%\end{equation}
To show that $v\in Core(T')$, we only need to show (by the concavity of $F_T(.)$ along any path) $F_{T'}(v) \geq F_{T'}(y)$  %\mnote{corrected F' to T'}
for any neighbor $y$ of $v$. Evidently $y\neq v$ and $F_{T'}(v) \geq F_{T'}(u)$, so we can assume $y \notin\{u,v\}$. Using a generalized notation  $F_H(a,b)$ for the number of subtrees of a tree $H$ containing {\em both} vertices $a,b$, we observe
\begin{equation}\label{eq:harlepes1}
F_{T'}(v) = F_T(v) - F_T(u,v) + F_{T\setminus\{u\}}(v) 
\end{equation}
and 
\begin{equation}\label{eq:harlepes2}
F_{T'}(y) = F_T(y) - F_T(u,y) + F_{T\setminus\{u\}}(v,y).
\end{equation}
If $y \in V(P_T(u,v))$, then we have
$$ F_{T\setminus\{u\}}(v) > F_{T\setminus\{u\}}(v,y) \hbox{ and } F_T(u,y) > F_T(u,v), $$
immediately implying that $\eqref{eq:harlepes1} > \eqref{eq:harlepes2}$ since $F_T(v) \geq F_T(y)$ (by the fact that $v \in Core(T)$).
Otherwise, $v \in V(P_T(u,y))$ and $y \neq x$. Let $S$ be the component containing $v$ in $(T\setminus\{u\}) \setminus \{vy\}$, then
$$ F_T(u,v) - F_T(u,y) = F_{T\setminus\{u\}}(x,v) - F_{T\setminus\{u\}}(x,y) = F_S(x,v) < 
F_S(v) = F_{T\setminus\{u\}}(v) - F_{T\setminus\{u\}}(v,y), $$
again implying $\eqref{eq:harlepes1} > \eqref{eq:harlepes2}$.
Hence the proof of Lemma~\ref{lem:min_vu1} is completed.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{lem:min_vu2}]
Observe
\begin{equation} \label{negylepes}
F_{T'}(v)=2F_{T\setminus\{u\}}(v) <2F_T(v).
\end{equation}
Also observe 
\begin{equation} \label{otlepes}
F_{T}(u)= 1+ \frac{F_{T}(x)}{2}\leq 1+\frac{F_T(v)-1}{2}.
\end{equation}
Hence by (\ref{negylepes}) and (\ref{otlepes}),
\begin{equation} \label{hatlepes}
F_{T'}(v) \Bigl(F_T(u)-\frac{F_T(v)}{2}\Bigl)\leq \frac{F_{T'}(v)}{2}<F_T(v).
%=2F_{T\setminus\{u\}}(v) <2F_T(v).
\end{equation}
Note that (\ref{hatlepes}) implies
\begin{equation} \label{hetlepes}
F_{T'}(v)F_{T}(u)< F_{T}(v)\Bigl( 1+   \frac{F_{T'}(v)}{2}  \Bigl)=F_{T}(v)F_{T'}(u),
\end{equation}
finishing the proof of  Lemma~\ref{lem:min_vu2}. 
\end{proof}

\bigskip
Based on Lemma~\ref{lem:min_vu3}, we represent $T$ that minimizes $R(T)$ 
 as $T_v \cup \{ uv \}$ (Fig.~\ref{fig:min_vu1}). We have
$$ \frac{F_T(v)}{F_T(u)} = \frac{ 2 F_{T_v}(v) }{1 + F_{T_v}(v)} = 2 - \frac{2}{1 + F_{T_v}(v)}, $$
and hence $R(T) $ is minimized when $F_{T_v}(v)$ is minimized.

Now we focus on $T_v$ and let the neighbors of $v$  in $T_v$ be $v_1, \ldots, v_k$. We claim $k\geq 2$. Indeed, if there is only one neighbor $v_1=w$, which separates a subtree $T_w$ from
$v$, like on Fig.~\ref{fig:min_vu1}  $v$ separates $T_v$ from $u$. It is easy to see that
$F_T(v)=2+2F_{T_w}(w)$ and $F_T(w)=3F_{T_w}(w)$, showing $v\notin Core(T)$
when $F_{T_w}(w)>2$,
a contradiction. This happens for all $n\geq 5$.



Hence $k\geq 2$, 
 and  let the  connected components in $T_v\setminus \{v\}$ be $T_1, \ldots, T_k$ (Fig.~\ref{fig:min_vu2}), such that $v_i$ is a vertex  of $T_i$. Assume without loss of generality that 
$$ F_{T_1}(v_1) \geq F_{T_i}(v_i) $$ for any $i$. 

\begin{figure}[htbp]
\centering
    \begin{tikzpicture}[scale=1]
        \node[fill=black,circle,inner sep=1pt] (t0) at (0,3) {};
        \node[fill=black,circle,inner sep=1pt] (t1) at (-1,2) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (-3,2) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (1,2) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (3,2) {};
        
        \draw (t0)--(t1);
        \draw (t0)--(t2);
        \draw (t0)--(t3);
        \draw (t0)--(t4);
        
        \draw (1,2)--(1.7,1)--(.3,1) -- cycle;
        \draw (3,2)--(3.7,1)--(2.3,1) -- cycle;
        \draw (-1,2)--(-1.7,1)--(-.3,1) -- cycle;
        \draw (-3,2)--(-3.7,1)--(-2.3,1) -- cycle;
        
        
        \node at (1,1.2) {$T_{k-1}$};
        \node at (3,1.2) {$T_{k}$};
        \node at (-1,1.2) {$T_{2}$};
        \node at (-3,1.2) {$T_{1}$};
        
        \node at (0,3.2) {$v$};
        \node at (-3.2,2.1) {$v_1$};
        \node at (-1.2,2.1) {$v_2$};
        \node at (1.3,2.1) {$v_{k-1}$};
        \node at (3.2, 2.1) {$v_k$};
        
        \draw [line width=0.3mm] [style=dotted] (-.2,1.4)--(.2,1.4);
        
        
     \end{tikzpicture}
\caption{$T_v$ and its subtrees.}\label{fig:min_vu2}
\end{figure}

First we formulate the condition for $v$ to be in the subtree core of $T$:

\begin{lemma}
With $T$ and $v$ represented above, $v \in Core(T)$ if and only if
\begin{equation}\label{eq:min_vu_cond}
2\prod_{{1\leq j \leq k}, {j\neq i}} (1 + F_{T_j}(v_j)) \geq F_{T_i}(v_i) 
\end{equation}
for any $1\leq i \leq k$.
\end{lemma}

\begin{proof}
By the strict concavity of $F_T(.)$ along any path, we have $v \in Core(T)$ if and only if
$ F_T(v) \geq F_T(y) $ for any neighbor of $v$. This inequality evidently holds when $y=u$.

For $y=v_i$ for some $1\leq i \leq k$, $F_T(v) \geq F_T(v_i)$ if and only if the number of subtrees containing $v$ but not $v_i$ is at least as large as the number of subtrees containing $v_i$ but not $v$. Notice that the former is
$$  2\prod_{{1\leq j \leq k}, {j\neq i}} (1 + F_{T_j}(v_j)), $$
and the latter is
$$ F_{T_i}(v_i), $$
completing the proof.
\end{proof}

Next we claim that $T_1$,  the heaviest branch in $T_v$  regarding $F_{T_i}(v_i)$, must be a path.

\begin{lemma}
To minimize $F_{T_v}(v)$, where $v\in Core(T)$ in  Fig.~\ref{fig:min_vu1}, $T_1$ must be a path
in  Fig.~\ref{fig:min_vu2}.
\end{lemma}

\begin{proof}
Suppose (for contradiction) that $T_1$ is not a path,  and let 
$$ P_{v_1,w}=w_0(v_1)w_1w_2\ldots w_{l-1}w_l (w) $$
be a longest path in $T_1$ from $v_1=w_0$ to some leaf $w=w_l$. (In other words, considering  $T_1$ as a rooted tree at $v_1$, it is of height $l$ and $w$ is one of the vertices of the greatest height.) Let $j$ ($ 0\leq j\leq l-1$) be the smallest integer such that $w_j$ has a neighbor $z$ {\em not} on $P_{v_1,w}$. 
Let $A_j, A_{j+1}, \ldots, A_{l-1}$ denote the connected components of $T_1 \setminus E(P_{v_1,w})$ containing $w_j, w_{j+1}, \ldots, w_{l-1}$ respectively. 
Define the tree $A_{\geq j+1} = A_{j+1} \cup A_{j+2} \cup \ldots \cup A_{l-1} \cup \{w\}$ with the edge
set $w_{j+1}w_{j+2},\ldots,w_{l-1}w_l$ added.


We will consider $T'_1$ obtained from $T_1$ by moving $A_j$ from $w_j$ to $w_{j+1}$ (Fig.~\ref{fig:min_vu3}), and the corresponding $T'_v$, $T' $ in the original problem. 

\begin{figure}[htbp]
\centering
    \begin{tikzpicture}[scale=1.5]

        \node[fill=black,circle,inner sep=1pt] (t1) at (1,0) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,0) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,0) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,0) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,0) {};
        \node[fill=black,circle,inner sep=1pt] (t6) at (6,0) {};
        
        \draw [style=dashed] (t1)--(t2);
        \draw (t2)--(t3);
        \draw [style=dashed] (t3)--(t4);
        \draw (t4)--(t5);
        \draw (t5)--(t6);
        
        \draw (5,0)--(5.3,-1)--(4.7,-1) -- cycle;
        \draw (4,0)--(4.3,-1)--(3.7,-1) -- cycle;
        \draw (3,0)--(3.3,-1)--(2.7,-1) -- cycle;
        \draw (2,0)--(2.3,-1)--(1.7,-1) -- cycle;

        \node at (6,.2) {$w(w_l)$};
        \node at (5,-.8) {$A_{l-1}$};
        \node at (5,.2) {$w_{l-1}$};
        \node at (4,-.8) {$A_{l-2}$};
        \node at (4,.2) {$w_{l-2}$};
        \node at (3,-.8) {$A_{j+1}$};
        \node at (3,.2) {$w_{j+1}$};
        \node at (2,-.8) {$A_j$};
        \node at (2,.2) {$w_j$};
        \node at (1,.2) {$v_1(w_0)$};

        
        \node at (-.7,-.5) {{\huge $T_1:$}};
        
        
        
        

        \node[fill=black,circle,inner sep=1pt] (t1) at (1,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t2) at (2,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t3) at (3,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t4) at (4,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t5) at (5,-3) {};
        \node[fill=black,circle,inner sep=1pt] (t6) at (6,-3) {};
        

        \draw [style=dashed] (t1)--(t2);
        \draw (t2)--(t3);
        \draw [style=dashed] (t3)--(t4);
        \draw (t4)--(t5);
        \draw (t5)--(t6);
        
        \draw (5,-3)--(5.3,-4)--(4.7,-4) -- cycle;
        \draw (4,-3)--(4.3,-4)--(3.7,-4) -- cycle;
        \draw (3,-3)--(3.3,-4)--(2.7,-4) -- cycle;
        \draw (3,-3)--(3.3,-2)--(2.7,-2) -- cycle;

        \node at (6,-2.8) {$w(w_l)$};
        \node at (5,-3.8) {$A_{l-1}$};
        \node at (5,-2.8) {$w_{l-1}$};
        \node at (4,-3.8) {$A_{l-2}$};
        \node at (4,-2.8) {$w_{l-2}$};
        \node at (3,-3.8) {$A_{j+1}$};
        \node at (3.4,-2.8) {$w_{j+1}$};
        \node at (3,-2.2) {$A_j$};
        \node at (2,-2.8) {$w_j$};
        \node at (1,-2.8) {$v_1(w_0)$};
                
        \node at (-.7,-3.5) {{\huge $T'_1:$}};
        
     \end{tikzpicture}
\caption{Generating $T'_1$ from $T_1$.}\label{fig:min_vu3}
\end{figure}

Then we have
\begin{equation}\label{eq:min_vu_comp1}
F_{T_1}(v_1) = j + F_{A_j}(w_j)\Bigl(1+F_{A_{\geq j+1}}(w_{j+1})\Bigl) 
\end{equation}
and
\begin{equation}\label{eq:min_vu_comp2}
F_{T'_1}(v_1) = j+1 + F_{A_j}(w_j)F_{A_{\geq j+1}}(w_{j+1}).
\end{equation}
%where $A_{\geq j+1} = A_{j+1} \cup A_{j+2} \cup \ldots \cup A_{l-1} \cup \{w\}$.
From \eqref{eq:min_vu_comp1} and \eqref{eq:min_vu_comp2}, it is easy to see that
$$ F_{T'_1}(v_1) \geq \frac12 F_{T_1}(v_1).$$
Hence, for any $i\neq 1$, we have
$$ F_{T_i}(v_i) \leq F_{T_1}(v_1) \leq 2 F_{T'_1}(v_1), $$
maintaining the condition \eqref{eq:min_vu_cond} in $T'$.
Also from \eqref{eq:min_vu_comp1} and \eqref{eq:min_vu_comp2}, we have
\begin{equation}\label{eq:min_vu_comp3}
F_{T'_1}(v_1) < F_{T_1}(v_1)
\end{equation}
since $F_{A_j}(w_j)>1$. Hence the condition \eqref{eq:min_vu_cond} is also maintained for $i=1$ in $T'$.

Thus $v \in Core(T')$. Furthermore, \eqref{eq:min_vu_comp3} implies that $F_{T'_v}(v) < F_{T_v}(v)$, a contradiction.
\end{proof}

We are now ready to  minimize $F_{T_v}(v)$ and to   characterize the structure with minimal $F_{T_v}(v)$. 
Assume  $x = |V(T_1)|$ (and consequently $F_{T_1}(v_1)=x$) and $|V(T)|=n\geq 5$.  Consider now $S=T_v \setminus  T_1$. 
\begin{lemma} \label{utas}
The inequality $\prod_{i=2}^k(1 + F_{T_i}(v_i)) \geq n-1-x$ holds. Equality holds if and only if 
$S$ is a path and $v$ is an endpoint of the path $S$.
\end{lemma}
\begin{proof}
It is easy to see that 
\begin{equation} \label{crude}
\prod_{i=2}^k(1 + F_{T_i}(v_i)) \geq 1+ \sum_{i=2}^k F_{T_i}(v_i) \geq |V(S)|=  n-1-x.
\end{equation}
All the terms of $1+ \sum_{i=2}^k F_{T_i}(v_i)  $ are present among the terms of expansion of
the left-hand side.
If equality holds, then the  $2^{k-1}$ terms on the left side  are these $k$ terms. This happens
if and only if $k=2$. In case of $k=2$ and equality in (\ref{crude}),  the same argument applies to
$S\setminus \{v\}$, etc., completing the characterization by induction.
%Furthermore, equality holds in (\ref{crude}) if and only if 
\end{proof}
We will need the following fact that is easy to verify by considering cases according to  $n$ modulo 3:
\begin{lemma} \label{egesz}
For a positive integer $n$, $n-1=\lceil \frac{x}{2}\rceil +x$ if and only if $x=\lfloor \frac{2}{3}(n-1) \rfloor$.
\end{lemma}
  %First we assume $3|n-1$ (the other cases are similar) and consider the following cases.
Now we consider cases.

\noindent {\bf Case (i):} $x \geq \lfloor  \frac23 (n-1) \rfloor$.\\ 
As  \eqref{eq:min_vu_cond} implies
$$ 2\prod_{i=2}^k(1 + F_{T_i}(v_i)) \geq x,$$
we have
\begin{equation} \label{foeset}
 F_{T_v}(v) = \prod_{i=1}^k (1 + F_{T_i}(v_i)) \geq \Bigl\lceil \frac{x}{2}\Bigl\rceil (x+1)
 \geq    \Bigl\lceil \frac{\lfloor  \frac23 (n-1) \rfloor}{2}\Bigl\rceil (1+  \lfloor  \frac23 (n-1) \rfloor).
 \end{equation}
% > \frac29 (n-1)^2 + \frac13 (n-1). $$
It is easy to see that if equation holds in (\ref{foeset}), then $\Bigl\lceil \frac{x}{2}\Bigl\rceil =\prod_{i=2}^k (1 + F_{T_i}(v_i))$ and $x=\lfloor  \frac23 (n-1) \rfloor$. By Lemma~\ref{utas}, $n-1-x \leq
\prod_{i=2}^k (1 + F_{T_i}(v_i))$, and hence 
\begin{equation} \label{lastineq}
n-1\leq x+ \Bigl\lceil \frac{x}{2}\Bigl\rceil.
\end{equation}
By Lemma~\ref{egesz}, formula (\ref{lastineq}) is solved by equality if and only if $x= \lfloor  \frac23 (n-1) \rfloor$, and with strict inequality if  and only if $x> \lfloor  \frac23 (n-1) \rfloor$.
Therefore, if equality holds in (\ref{foeset}), then $x= \lfloor  \frac23 (n-1) \rfloor$, and by
 Lemma~\ref{utas}, $k=2$ and $T_2$ is a path. The description above is a construction 
 that always realizes the lower bound in the  right-hand side of  (\ref{foeset}).
 
 

Our goal is to conclude that the minimum of  $F_{T_v}(v)$ is what we realized as the minumum for Case (i) in (\ref{foeset}).

\noindent {\bf  Case (ii):} $\frac13 (n-1) \leq x \leq \lfloor  \frac23 (n-1) \rfloor-1$.\\
By Lemma~\ref{utas}, $ F_S(v) \geq |V(S)| = n-1-x $, and hence 
\begin{equation} \label{quadr}
 F_{T_v}(v) \geq (n-1-x)(x+1) =g(x).
\end{equation}
The lower bound for $F_{T_v}(v) $ in this case is a quadratic function of $x$, which is minimized
in one of the endpoints of the interval. Easy calculations show
$$g\Bigl(   \frac13 (n-1)  \Bigl)> \Bigl\lceil \frac{\lfloor  \frac23 (n-1) \rfloor}{2}\Bigl\rceil (1+  \lfloor  \frac23 (n-1) \rfloor)   \hbox{  and  } g\Bigl(   \lfloor  \frac23 (n-1) \rfloor-1  \Bigl)> \Bigl\lceil \frac{\lfloor  \frac23 (n-1) \rfloor}{2}\Bigl\rceil (1+  \lfloor  \frac23 (n-1) \rfloor), $$
showing that   the minimum in Case (i) cannot even be matched in Case (ii). 


\noindent {\bf Case (iii):}  $x=1$.\\
This means $T_1=v_1$. By the choice of $T_1$, $T_i=v_i$ for $i=1,2,\ldots,k$, and hence $T_v$ is
a star.  By Lemma~\ref{lem:T_v_star}, $F_{T_v}(v)=2^{n-2}$, exceeding the right-hand side of
(\ref{foeset}) for $n\geq 5$. 

\noindent {\bf Case (iv):}  $2\leq x < \frac13 (n-1)$.\\
As $2\leq x$, there is a leaf  $w$ in $T_1$ that is not $v_1$. We consider subcases.

{\bf Subcase (iv)(a):} \\
For $i=2,\ldots,k$, $T_i=v_i$. Then easy calculation gives $F_{T_v}(v)=(x+1)2^{n-2-x}$. This number 
exceeds the right-hand side of
(\ref{foeset}) for $n\geq 5$. 

{\bf Subcase (iv)(b):} \\
Without loss of generality, assume that there is a leaf
 $z\neq v_2$   in $T_2$ and $y$ its unique neighbor. 

Obtain a tree  $T'_v$ by removing the  $\{yz\}$ edge from $ T_v$ and adding the   $\{wz\}$ edge. Then \eqref{eq:min_vu_cond} is maintained for $T'_v$, so it is a legitimate candidate to minimize 
$F_{T_v}(v)$, as in Case (iv)
$$ x+1 < n-1 - (x+1) \leq \prod_{i=2}^k(1 + F_{T_i}(v_i)). $$
Furthermore,
\begin{align*}
F_{T'_v}(v) 
&\leq  (x+2)F_{T_2}(v_2) \prod_{i=3}^k (1+F_{T_i}(v_i)) \\
&< (x+1)(1+F_{T_2}(v_2)) \prod_{i=3}^k (1+F_{T_i}(v_i))\\
&= F_{T_v}(v) 
\end{align*}
since $x\geq F_{T_2}(v_2)$. Hence this case will not obtain the minimum of $F_{T_v}(v)$.






     
\begin{thebibliography}{10}
 
 \bibitem{adam} A.~\'Ad\'am.  \newblock The centrality of vertices in trees. \newblock
{\em Studia Sci. Math. Hung.} 9:285--303, 1974.

 
  \bibitem{barefoot}  C.A.~Barefoot, R.C.~Entringer, and L.A.~Sz\'ekely. \newblock
 Extremal values for ratios of distances in trees. \newblock 
{\em Discrete Appl. Math.} 80:37--56, 1997.

\bibitem{cela} E.~Cela, N.S.~Schmuck, S.~Wimer, and G.J.~Woeginger. \newblock The Wiener maximum quadratic assignment problem. \newblock {\em Discrete Optim.} 8:411--416, 2011.


\bibitem{rulebased} M.H.~Chehreghani,  % Mostafa Haghir
M.H.~Chehreghani, 
%Morteza Haghir  
C.~Lucas,  M.~Rahgozar, and E.~Ghadimi. \newblock 
 Efficient rule based structural algorithms for classification of tree structured data. \newblock {\em Intelligent Data Analysis,}   13(1):165--188, 2009.
 
 \bibitem{czabarkawagner} \'E.~Czabarka,  L.A.~Sz\'ekely, and S.~Wagner. \newblock The inverse problem for
certain tree parameters. \newblock  {\em Discrete Applied Math.}
157(15):3314--3319, 2009.
 
 \bibitem{hardness}  M.J.~Dinneen and M.~Khosravani. \newblock 
Hardness of Approximation and Integer Programming Frameworks for Searching for Caterpillar Trees. \newblock
 CDMTCS Research Reports CDMTCS-394 (2010), \url{https://researchspace.auckland.ac.nz/handle/2292/10547}


\bibitem{gutman}
A.A.~Dobrynin, R.C.~Entringer, and I.~Gutman. \newblock 
Wiener index of trees: Theory and applications. \newblock
 {\em Acta Appl. Math.} 66(3):211--249, 2001.

\bibitem{ejs} R.C.~Entringer,  D.E.~Jackson, and D.A.~Snyder. \newblock 
Distance in graphs. \newblock {\em Czechoslovak Math. J.} 26(101):283--296, 1976.

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


\bibitem{hamina}  M.~Hamina and M.~Peltola. \newblock Least central subtrees, center, and centroid of a tree. \newblock
{\em Networks,}  57(4):328--332, 2011.

\bibitem{hamina2}  M.~Hamina and M.~Peltola. \newblock  
Some structural properties of a least central subtree of a tree. \newblock {\em Algorithmic Operations Research}, 
5(2), 2010.


\bibitem{maxmatchings}
C.~Heuberger and S.G.~Wagner. \newblock The number of maximum matchings in a tree. \newblock
{\em Discrete Math.} 311(21):2512--2542, 2011.
%doi:  10.1016/j.disc.2011.07.028
%PMCID: PMC3226351

\bibitem{indepsubsets}
C.~Heuberger and S.G.~Wagner. \newblock Maximizing the number of independent subsets over trees with bounded degree. \newblock
{\em J. Graph Theory,}  58(1):49--68, 2008.


%
\bibitem{prodinger} C.~Heuberger and H.~Prodinger. \newblock On $\alpha$-greedy
expansions of numbers. \newblock  {\em Adv. in Appl. Math.} 38(4):505--525, 2007.




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


\bibitem{jordan} C.~Jordan. \newblock  Sur les assemblages de lignes. \newblock {\em J. Reine
Angew. Math.} 70:185--190, 1869.

\bibitem{hardness2}   M. Khosravani. \newblock Searching for Optimal Caterpillars in General and Bounded Treewidth Graphs. \newblock
Ph.D. Thesis, University of Auckland, 2011.

\bibitem{dan} B.~Knudsen. \newblock   Optimal multiple parsimony alignment with
affine gap cost using a phylogenetic tree. \newblock  {\em Lecture Notes in Bioinformatics,} 2812:433--446, Springer Verlag, 2003.
 
 \bibitem{lepovic1998collective}
M.~Lepovi\'c and I.~Gutman.
\newblock {A} {c}ollective {p}roperty of {t}rees and {c}hemical {t}rees.
\newblock {\em J. Chem. Inf. Comput. Sci.}, 38:823--826, 1998.
 
 \bibitem{shuchao}
Shuchao Li and Shujing Wang. \newblock Further analysis on the total number of subtrees of trees. \newblock
arXiv:1204.6152, 2012 

\bibitem{shuchao2}
Shuchao Li and Shujing Wang. \newblock Enumerating the total number of subtrees of trees. \newblock
arXiv:1206.2975, 2012 

 
 \bibitem{lovasz} L. Lov\'asz. \newblock  {\em Combinatorial Problems and Exercises},
2nd ed., North--Holland Publishing Co., Amsterdam, 1993.
 
 \bibitem{maunz} A.~Maunz, C.~Helma, and S.~Kramer. \newblock Efficient mining for structurally diverse subgraph patterns in large molecular databases. \newblock 
{\em Machine Learning,}
83(2):193--218, 2011.%DOI: 10.1007/s10994-010-5187-6

\bibitem{speedup}  M.~Schmidt and  A.~Sch\"obel. \newblock Location of speed-up subnetworks. \newblock
 Institut f\"ur Numerische und Angewandte Mathematik, Nr. 2009-13,  Georg-August Universit\"at 
 G\"ottingen.

\bibitem{nina} N.~Schmuck, S.~Wagner, and H.~Wang. \newblock Greedy trees, caterpillars, and Wiener-type graph invariants. \newblock {\em MATCH Commun.Math.Comput.Chem.} 68(1):273--292, 2012.  

\bibitem{subtrees} L.A.~Sz\'ekely and Hua Wang. \newblock On subtrees of trees. \newblock
 {\em Adv. Appl. Math.} 34:138--155, 2005.

\bibitem{congnum} L. A. Sz\'ekely and Hua Wang. \newblock Binary trees with the
 largest number of
subtrees with at least one leaf. \newblock
 {\em Congr. Numer.} 177:147--169, 2005.

\bibitem{largest}
L.A.~Sz\'ekely and Hua Wang. \newblock Binary trees with the largest number of
subtrees. \newblock   {\em Discrete Appl. Math.}  155(3):374--385, 2006.

\bibitem{sibling} L.A.~Sz\'ekely and Hua Wang. \newblock
Extremal values of ratios: distance problems vs. subtree problems in trees II. \newblock To appear.

\bibitem{taoyang} L. A.~Sz\'ekely, Hua Wang, and Taoyang Wu. \newblock The sum of distances between the leaves of a tree
and the 'semi-regular' property. {\em Discrete Math.} 311:1197--1203, 2011.

\bibitem{self-similar} E.~Teufl and
S.G.~Wagner. \newblock Enumeration problems for classes of self-similar graphs	{\em J. Combinatorial Theory, Series A},
114(7):1254--1277, 2007.

\bibitem{wagner2006class}
S.~Wagner.
\newblock A class of trees and its {W}iener index.
\newblock {\em Acta Appl. Math.}, 91(2):119--132, 2006.

\bibitem{wagner2008molecular}
S.~Wagner, Hua Wang, and Gang Yu.
\newblock Molecular graphs and the inverse {W}iener index problem.
\newblock {\em Discrete Applied Mathematics}, 157(7):1544--1554, 2009.



\bibitem{correl} S.~Wagner. \newblock Correlation of graph-theoretical indices. \newblock
{\em SIAM J. Discrete Mathematics},  21(1):33--46, 2007.

\bibitem{degreeseq} Hua Wang. \newblock The extremal values of the Wiener index of a tree with given degree sequence. \newblock {\em Discrete Appl. Math.} 156(14):2647--2654, 2008. Corrigendum,{\em Discrete Appl. Math.} 157(18):3754, 2009.



\bibitem{fortynine} Hua Wang and Gang Yu. \newblock
All but 49 numbers are Wiener indices of trees. \newblock  {\em Acta
Appl. Math.} 92(1):15--20, 2006. 


\bibitem{wiener} H.~Wiener. \newblock Structural determination of paraffin boiling points. \newblock {\em J. Am. Chem. Soc.} 
1(69):17--20, 1947.

\bibitem{yanyeh} Weigen Yan and Yeong-Nan Yeh. \newblock Enumeration of subtrees of trees. \newblock
{\em Theoretical Computer Science},  369(1-3):256--268, 2006.

\bibitem{zelinka} B. Zelinka. \newblock Medians and peripherans of trees. \newblock {\em Arch. Math.} (Brno) 4:87--95, 1968.

\bibitem{zhang2008} Xiao-Dong~Zhang, Q.-Y.~Xiang, L.-Q.~Xu, and R.-Y.~Pan. \newblock The Wiener index of trees with given degree sequences. \newblock {\em MATCH Commun.Math.Comput.Chem.}, 60:623--644, 2008.

\bibitem{zhang2010} Xiao-Dong~Zhang,  Yong~Liu, and Min-Xian~Han. \newblock Maximum Wiener Index of Trees with
Given Degree Sequence. \newblock {\em  MATCH Commun.Math.Comput.Chem.},
64:661--682, 2010.

\bibitem{gray} Xiu-Mei Zhang,
Xiao-Dong Zhang,
D. Gray, and Hua Wang. \newblock The number of subtrees of trees with given degree sequence. \newblock
{\em J. Graph Theory}, (2012)
DOI: 10.1002/jgt.21674


\end{thebibliography}

\end{document}
































