\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}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}