\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.24}{24(1)}{2017} \usepackage{amsmath,amssymb,amsthm} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \numberwithin{equation}{section} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\dist}{{\rm dist}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf On the number of $r$-matchings in a tree} \author{Dong Yeap Kang\thanks{Supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT \& Future Planning (2011-0011653).}\\ \small Department of Mathematical Sciences\\[-0.8ex] \small KAIST\\[-0.8ex] %\small 291 Daehak-ro Yuseong-gu \\ \small Daejeon, South Korea.\\ \small\tt dynamical@kaist.ac.kr\\ \and Jaehoon Kim \thanks{Supported by the European Research Council under the European Union's Seventh Framework Programme (FP/2007--2013) / ERC Grant Agreements no. 306349.}\\ \small School of Mathematics\\[-0.8ex] \small University of Birmingham\\[-0.8ex] \small Birmingham, United Kingdom.\\ \small\tt kimJS@bham.ac.uk, mutualteon@gmail.com\\ \and Younjin Kim \thanks{Supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (2009-0093827).} \\ \small Institute of Mathematical Sciences\\[-0.8ex] \small Ewha Womans University\\[-0.8ex] %\small 52 Ewhayeodae-gil, Seodaemum-gu, \small Seoul, South Korea.\\ \small\tt younjinkim@ewha.ac.kr \\ \and Hiu-Fai Law \\ \small The Wong School of Finite Geometry\\[-0.8ex] \small Hong Kong\\ \small\tt hiufai.law@gmail.com } \date{\dateline{Dec 15, 2016}{Jan 23, 2017}{Feb 3, 2017} \\ \small Mathematics Subject Classifications: 05C30, 05C69, 05C70} \begin{document} \maketitle \begin{abstract} An $r$-matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$. This generalizes both matchings and induced matchings as matchings are $1$-matchings and induced matchings are $2$-matchings. In this paper, we estimate the minimum and maximum number of $r$-matchings in a tree with fixed order. \bigskip\noindent \textbf{Keywords:} matching; independent set; tree \end{abstract} \section {Introduction}\label{intro} A set of vertices in a graph $G$ is an {\it independent set} if no two vertices in the set are adjacent in $G$. The number of independent sets in $G$ is denoted by $i(G)$, and it has been studied extensively. Kleitman and Winston proved an upper-bound on $i(G)$ for graphs $G$ and the upper-bound has been used to count the number of lattices \cite{KW80} and graphs without cycles of length four \cite{KW82}, and variations of their method were used to prove an upper bound of $i(G)$ for regular graphs $G$ \cite{A91, S01} and to count the number of sum-free sets in abelian group \cite{A91, LLS01}. Many extremal results on $i(G)$ have been obtained over various families of graphs such as trees \cite{PT82}, regular graphs \cite{Z10} and graphs with minimum degree \cite{CR14}. Also the parameter $i(G)$ is studied under the name {\it Merrifield-Simmons index} in chemistry \cite{MS89} and which is related to Hard Models in physics \cite{BET80, K01, SS05}. Instead of independent set of vertices, one can consider a similar concept for edges. A set of edges in a graph $G$ is a {\it matching} if no two edges in the set are incident in $G$. Again, the number of matchings has been drawn much attention and results on the number of matchings or the number of given size matchings have been obtained for various families of graphs such as trees \cite{W07}, bipartite graphs \cite{B73, M63} and regular bipartite graphs \cite{C14}. The number of matchings is also known as {\it Hosoya index} in mathematical chemistry \cite{GP86, H86} and is also connected to the {\it monomer-dimer model} of statistical physics \cite{HL72}. There are many results concerning the number of matchings in several classes of trees or tree-like graphs (see \cite{WG10}). In particular, it is well known that the following is true. \begin{fact}\label{fact 1}\cite{G77, WG10} The minimum and maximum number of matchings among all $n$-vertex trees are attained only by the star and the path, respectively. \end{fact} For two edges $e=uv$ and $e'=u'v'$ in $G$, let $\dist_{G}(e,e')$, {\it the distance} between $e$ and $e'$ be the length of shortest paths between $\{u,v\}$ and $\{u',v'\}$ in $G$. Here, the length of the path $P$ is the number of edges in $P$ while we denote $|P|$ the number of vertices in $P$. In \cite{Law12}, the following natural generalization of matchings is considered. We say a collection $M$ of edges of graph $G$ is an {\it $r$-matching} if $$\dist_{G}(e,e')\geq r \text{ for all distinct edges }e,e' \in M.$$ Then $1$-matchings are matchings, and $2$-matchings are induced matchings. Purpose of this paper is to generalize Fact~\ref{fact 1} from $1$-matchings to $r$-matchings for $r\geq 2$. In other words, we are interested in determining the maximum and the minimum number of $r$-matchings in a tree of fixed order. In fact, we show that the generalization of Fact~\ref{fact 1} holds for $r=2$ while it does not hold for $r\geq 10$. For a graph $G$, let $s_r(G)$ be the number of $r$-matchings in $G$. Let $\mathbf{T}_{n}$ be the family of all trees with $n$ vertices, and $P_n$ be an $n$-vertex path. The term $\log$ denotes the natural logarithm. For two graphs $G$ and $H$, $G\cup H$ denotes the vertex disjoint union of $G$ and $H$. Note that the following simple observation is easy. \begin{observation}\label{union} For a positive integer $r$ and two graphs $G$ and $H$, $$s_r(G\cup H) = s_r(G)\cdot s_r(H).$$ \end{observation} The following observation shows that finding the minimum is easy. Hence, we focus on estimating the maximum number of $r$-matchings in a tree of fixed order. Since stars are exactly the trees with diameter two, the following observation generalizes Fact~\ref{fact 1} for the minimum value. \begin{observation}\label{observation} For $T \in \mathbf{T}_{n}$, we have $\displaystyle \min_{T\in \mathbf{T}_{n}}s_r(T) = n$, and the equality holds only for trees $T$ with diameter at most $r+1$. \end{observation} \begin{proof} Since the empty set and every set of exactly one edge are $r$-matchings, we have $s_r(T) \geq n$ for all $n$-vertex trees $T$. On the other hand, for any tree with diameter at most $r+1$, every $r$-matching can have at most one edge, we have $\displaystyle \min_{T\in \mathbf{T}_{n}}s_r(T) = n$. Note that a tree $T$ satisfying the equality must have no two edges with distance at least $r$, otherwise $T$ contains more than $n$ distinct $r$-matchings. Thus the tree $T$ with the equality must have diameter at most $r+1$.\end{proof} In Section \ref{path}, we estimate the number of $r$-matchings in the $n$-vertex path $P_n$. In Section \ref{induced}, we prove that the path $P_n$ contains the largest number of $2$-matchings (induced matchings) among all $n$-vertex trees, which generalizes Fact~\ref{fact 1} for $r=2$. In Section \ref{big r}, we analyze $\max_{T \in \mathbf{T}_{n}} s_r(T)$ in terms of $r$ and $n$ for $r,n \geq 2$ and prove upper and lower bounds for $ \max_{T \in \mathbf{T}_{n}} s_r(T)$. %that for $r \geq 2$ and $n\in \mathbb{N}$, $$ \frac{(2+o(1))\log r}{r}(e^{-\frac{6\log(r+1)}{r^2}}\alpha_r)^{n-1} \leq \max_{T \in \mathbf{T}_{n}} s_r(T) \leq \frac{(1+o(1))r}{2\log r}(e^{\frac{1}{r}}\alpha_r)^{n-1}.$$ %where $\alpha_r = (s+1)^{\frac{1}{r/2+s}} = e^{\frac{1}{s+1}}$ and $s = s(r)$ is a real number satisfying $r/2+s = (s+1)\log(s+1)$, thus $s = (1+o(1))\frac{r}{2 \log r}$. Throughout the paper, the term $o(1)$ represents a function of $r$ which approaches to $0$ as $r\rightarrow \infty$, unless specified otherwise. In Section~\ref{sec: appendix}, we prove that there are $n$-vertex trees having more $r$-matchings than $P_n$ when $r\in \mathbb{N} \backslash \{1,2,3,4,5,7,9\}$, which implies that Fact~\ref{fact 1} cannot be extended to $r$-matchings when $r\geq 10$. \section{ The number of $r$-matchings in $P_{n}$. } \label{path} Let $[n]$ be the set $\left \{1,\dots, n \right \}$ for a positive integer $n$, and $|G|$ be the number of vertices in a graph $G$. In this section, we discuss the asymptotic behavior of $s_r( P_n)$ as $n$ $\to \infty$ for a positive integer $r$. For the sake of formality, we let $s_r(P_{n})=1$ for $n = 0$. As $P_n$ has a natural linear order of the edges, let $e$ be the first edge of $P_n$. We have the following recurrence relation of $s_r(P_{n})$ by considering $r$-matchings that contains $e$ and does not contain $e$. \begin{equation} \label{initial values} s_r (P_{n} ) = n \text{ for } 1 \leq n \leq r+1, \end{equation} \begin{equation} \label{recurrence} s_r (P_{n} ) = s_r (P_{n-1} ) + s_r (P_{n-r-1} ) \text{ for } n \geq r+2. \end{equation} \\ Let $p_r(x) = x^{r+1} - x^{r} - 1 \in \mathbb{C}[x]$ be the characteristic polynomial for the recurrence relation (\ref{recurrence}). Since $p_r(x)$ and its derivative $p'_r(x)$ do not have any common root in $\mathbb{C}$, the polynomial $p_r(x)$ is separable. Let $q_1, q_2, \ldots, q_{r+1}$ be the $r+1$ distinct roots of $p_r(x)$ in $\mathbb{C}$, where $|q_1| \geq |q_2| \geq \cdots \geq |q_{r+1}|$. \begin{theorem}\label{lem:lemma1} The polynomial $p_r(x)$ has a real root $\beta_r$, with the following properties. \begin{itemize} \item[(i)] $\beta_r$ is the only real root of $p_r(x)$ bigger than 1, and is bigger than $|q|$ for any other roots $q$ of $p_r(x)$. \item[(ii)] We have $\beta_r^{r} = (1+o(1))\frac{r}{\log{r}}$. In particular, $\beta_r = \exp\left((1+o(1))\frac{\log r}{r}\right)$. \item[(iii)] There exists a constant $C_r >0 $ such that $$C_r = \lim_{n \to \infty}{\frac{s_r(P_n)}{\beta_r^{n-1}}} = \frac{\beta_r^{2r}}{\beta_r^{r} + (r+1)} = (1+o(1))\frac{r}{(\log{r})^2}.$$ \end{itemize} \end{theorem} \begin{proof} We first claim that $p_r(x)$ has only one real root $\beta_r$ bigger than $1$. Since $p_r(1) < 0$, $p_r(2) > 0$, and $p_r(x)$ is increasing for $x > \frac{r}{r+1}$, there is exactly one root $\beta_r$ of $p_r(x)$ in $(1,\infty)$ and $\beta_r \in (1,2)$. Next, we claim that $\beta_r$ has larger modulus than that of all other roots of $P_r(x)$; in particular, $\beta_r = q_1 > |q_2| \geq \cdots \geq |q_{r+1}|$, where $q_1, \dots, q_{r+1}$ are $r+1$ distinct roots of a separable polynomial $p_r(x) \in \mathbb{C}[x]$. %Every real root $q$ of $p_r(x)$ satisfies $q^r = \frac{1}{q-1}$, thus either $1 1$, $\beta_r$ is bigger than $|q|$ of all other real roots $q$. For every non-real root $q$ of $p_r(x)$ and every negative real root $q$ of $p_r(x)$, since $q = q^{r+1}/q^{r} \notin [0,\infty)$, we have $$p_r(\beta_r) = \beta_r^{r+1}-\beta_r^r -1 =|q^{r+1}-q^{r}| -1 > |q^{r+1}|-|q^{r}| -1 =|q|^{r+1}-|q|^r -1 = p_r(|q|).$$ Since $p_r (x)$ is an increasing function for $x \geq 1$, this implies that either $|q|\leq 1$ or $\beta_r > |q|$. Since $\beta_r>1$, in either case, we have $\beta_r > |q|$. This with the fact that $\beta_r$ is the only positive real root of $p_r(x)$ bigger than $1$ implies (i). Now we prove that \begin{align}\label{eq: first} \beta_r^{r} = (1+o(1))\frac{r}{\log{r}}. \end{align} Note that for large $r$, both $(\frac{r}{\log{r}})^{1/r}$ and $ (1+ \frac{1}{\sqrt{\log r}})$ are real numbers between $1$ and $2$ and $p_r(x)$ is increasing function for $x\geq 1$. Thus, in order to show \eqref{eq: first}, it is enough to verify the following two inequalities for large $r$. \begin{equation}\label{eq1} p_r \left( \left(\frac{r}{\log{r}}\right)^{1/r} \right)< 0 \end{equation} \begin{equation}\label{eq2} p_r \left( \left(\left(1+ \frac{1}{\sqrt{\log r}}\right)\frac{r}{\log{r}}\right)^{1/r} \right)>0 \end{equation} We get the inequality (\ref{eq1}) because the following holds: \begin{align*} \log(r)( p_r \left(\left(\frac{r}{\log{r}}\right)^{1/r} \right)+1)&= r\left(\left(\frac{r}{\log{r}}\right)^{1/r}-1\right) = r(e^{\frac{1}{r}(\log{r}-\log{\log{r}})}-1)\\ &= r\left( \frac{\log r - \log \log r}{r} + O\left(\frac{\log^2 r}{r^2}\right) \right) \\ &= \log{r}-\log\log{r}+o(1) < \log{r}. \end{align*} We also get the inequality (\ref{eq2}) because the following holds: \begin{align*} \log(r)(p_r \left( \left(\left(1+ \frac{1}{\sqrt{\log{r}}}\right)\frac{r}{\log{r}}\right)^{1/r} \right)+1) & \geq r\left(1+\frac{1}{\sqrt{\log{r}}}\right)\left(\left( \frac{r}{\log{r}}\right)^{1/r}-1\right) \\ &= r\left(1+\frac{1}{\sqrt{\log{r}}}\right)(e^{\frac{1}{r}(\log{r}-\log{\log{r}})}-1) \\ &\geq r\left(1+\frac{1}{\sqrt{\log{r}}}\right)\left( \frac{\log r - \log \log r }{r}\right) \\ & \geq \log{r}+\sqrt{\log{r}}-\log \log r - o(1) > \log{r}. \end{align*} Thus we obtain (ii). % In particular, as $r \log \beta_r = \log r - \log \log r + o(1)$, we have $\beta_r = (1 + o(1)) \exp(\frac{\log r - \log \log r}{r}) = \exp((1+o(1)) \frac{\log r}{r})$. Now we show that there exists $C_r > 0$ such that $\lim_{n \to \infty}{\frac{s_r(P_n)}{\beta_r^{n-1}}} = C_r$. We use an induction on $n$. Because we have $s_r(P_m)>0$ for every $m \geq 0$, there exists $c>0$ such that the following \eqref{eq: sr geq beta} holds for $0 \leq m \leq r+1$. \begin{align}\label{eq: sr geq beta} s_r(P_m)\geq c\beta_r^{m-1}. \end{align} For $n \geq r+2$, we assume that \eqref{eq: sr geq beta} holds for $1 \leq m \leq n-1$. By the recurrence relation (\ref{recurrence}), $$s_r(P_n) =s_r(P_{n-1}) + s_r(P_{n-r-1}) \geq c(\beta_r^{n-2} + \beta_r^{n-r-2}) = c\beta_r^{n-1}.$$ This inductively shows that \eqref{eq: sr geq beta} for all natural number $m$. Since $p(x)$ is separable, there exist $b_1, \dots, b_{r+1} \in \mathbb{C}$ such that $s_r(P_n) = b_1 \beta_r^{n-1}+ \sum_{i=2}^{r+1}{b_i {q_i}^{n-1}}$ for $n \geq 0$. Then we have a real number $$C_r = \lim_{n \to \infty}{\frac{s_r(P_n)}{\beta_r^{n-1}}}= b_1 \geq c > 0.$$ since $\beta_r > |q_i|$ for $2 \leq i \leq r+1$. Finally we estimate the value of $C_r$. For $n\geq 2r+1$, consider an $r$-matching $M$ in $P_{2n-1}= v_1\dots v_{2n-1}$. Let $e_i:= v_i v_{i+1}$. For $0\leq i\leq r-1$, if $M$ contains an edge $e_{n-r+i}$, then $M$ does not contain $e_j$ for any $j$ such that $n-2r+i\leq j \leq n+i$. Thus $M-e_{n-r+i}$ is an $r$-matching in the disjoint union of two paths $v_1\dots v_{n-2r+i}$ and $v_{n+i+1}\dots v_{2n-1}$. From this and Observation~\ref{union}, we conclude that for $0\leq i\leq r-1$ the number of $r$-matchings in $P_{2n-1}$ containing $e_{n-r+i}$ is $s_r(P_{n-2r+i} \cup P_{n-i-1})=s_r(P_{n-2r+i})s_r(P_{n-i-1})$. On the other hand, if $M$ does not contain any edge $e_{n-r+i}$ for $0\leq i\leq r-1$, then it is an $r$-matching in the disjoint union of two paths $v_1\dots v_{n-r}$ and $v_{n}\dots v_{2n-1}$. Thus by Observation~\ref{union}, the number of $r$-matchings in $P_{2n-1}$ not containing any edges $v_{n-r+i}v_{n-r+i+1}$ for $0\leq i\leq r-1$ is $s_r(P_{n-r})s_{r}(P_n)$. Thus $$s_r(P_{2n-1}) = s_r(P_{n-r})s_r(P_{n}) + \sum_{i=0}^{r-1}s_r(P_{n-2r+i})s_r(P_{n-i-1})$$ $$ = (1+o(1))({C_r}^2 \beta_r^{2n-r-2} + r{C_r}^2 \beta_r^{2n - 2r-3}).$$ Here $o(1) \rightarrow 0$ as $n \rightarrow \infty.$ Then we have \begin{eqnarray*} C_r &=&\lim_{n \to \infty}\frac{s_r(P_n)^2}{s_r(P_{2n-1})} = \lim_{n \to \infty}\frac{(1+o(1))C_r^2 \beta_r^{2n-2}}{(1+o(1))({C_r}^2 \beta_r^{2n-r-2} + r{C_r}^2 \beta_r^{2n - 2r-3})} \\ &=& \frac{\beta_r^{2r}}{\beta_r^{r} + r} \stackrel{\eqref{eq: first}}{=} (1+o(1))\frac{r}{(\log{r})^2}. \end{eqnarray*} Here, $o(1)$ on the first line approaches to $0$ as $n\rightarrow \infty$. \end{proof} \section{Trees with the maximum number of induced matchings} \label{induced} In this section, we prove that the path of order $n$ contains the largest number of induced matchings among all trees of order $n$. First of all, we prove the following lemma. Recall that a tree $T$ is not a path if and only if $T$ contains a vertex of degree at least three. \begin{lemma} \label{lem} Let $r \geq 2$ be an integer and $T$ be an $n$-vertex tree which is not a path. Let $T_0$ be a minimal subtree of $T$ containing all vertices of degree at least three. For any leaf $v$ of $T_0$, let $P_1$ and $P_2$ be any two distinct components of $T-v$ such that both $P_1$ and $P_2$ are paths and $|P_1| \geq |P_2|$. One of the following holds. \begin{itemize} \item[(P1)] $|P_1|\geq r+1$ \item[(P2)] $|P_1|\leq r$ and $|P_1|+|P_{2}| >r+1$ \item[(P3)] There exists an $n$-vertex tree $T'$ with $s_r(T')\geq s_r(T)$ and the number of leaves in $T'$ is less than $T$. Moreover, if $n\geq r+3$ and $T$ has exactly three leaves, then $s_r(P_n)> s_r(T)$ holds. \end{itemize} \end{lemma} \begin{proof}{ Suppose that (P1) and (P2) does not hold. Let $P_1:= v_1\cdots v_{p_1}$ and $P_2:= u_1\cdots u_{p_2}$ such that $v_1, u_1 \in N_{T}(v)$. Let both $u_0$ and $v_0$ denote the vertex $v$. Note that $v, P_1$ and $P_2$ together induces a path of $p_1+p_2+1\leq r+2$ vertices in $T$. We construct a new tree $T'$ from $T$ by replacing $vu_1$ with $u_1 v_{p_1}$. It is obvious that $T'$ contains exactly one less leaf than $T$. Let $$L= E(P_1) \cup E(P_2) \cup \{vv_1, vu_1\}.$$ For each $e\in E(T)$, consider the following bijection $f$ from $E(T)$ to $E(T')$. $$f(e):= \left\{ \begin{array}{ll} e & \text{ if } e\neq vu_1 \\ u_1v_{p_1} & \text{ if } e=vu_1. \end{array}\right.$$ For a collection $M$ of edges in $E(T)$, let $f(M):=\{f(e): e\in M\}$. Since $v, P_1$ and $P_2$ together induces a path of $p_1+p_2+1\leq r+2$ vertices in $T$, any two edges in $L$ have distance at most $r-1$ in $T$, thus \begin{equation}\label{eq: M cap L 1} \begin{minipage}[c]{0.8\textwidth}\em for any $r$-matching $M$ of $T$, $|M \cap L|\leq 1$. \end{minipage} \end{equation} Note that $\dist_T(e,e') =\dist_{T'}(f(e),f(e'))$ holds for $e,e'\notin L$. It is also easy to check that for $e\in L$ and $e'\in E(T)\setminus L$, we have $\dist_{T'}(f(e),f(e')) \geq \dist_{T}(e,e')$. This with \eqref{eq: M cap L 1} implies that if $M$ is an $r$-matching in $T$, then $f(M)$ is also an $r$-matching in $T'$. Since $f$ is a bijection between $E(T)$ and $E(T')$, this naturally gives $$s_r(T')\geq s_r(T).$$ If $n \geq r+3$ and $T$ has exactly three leaves, then $T'$ is a path with at least $r+3$ vertices, then we consider an edge $e$ that has distance exactly $r$ from $f(u_{p_2-1}u_{p_2})$ in $T'$. Since any two edges in $f(L)$ has distance at most $r-1$, we have $e\notin f(L)$ and $f(e)=e$. Thus $$\dist_{T}( u_{p_2-1}u_{p_2},e) = \dist_{T'}( f(u_{p_2-1}u_{p_2}), e) - p_1 =r -p_1 \leq r-1.$$ Thus $\{u_{p_2-1}u_{p_2}, e\}$ is not an $r$-matching in $T$ while $\{f(u_{p_2-1}u_{p_2}),e\}$ is an $r$-matching in $T'$. Thus $T'=P_n$ has strictly more $r$-matchings than $T$ and we obtain (P3). }\end{proof} The following claim easily follows from the recurrence relation~(\ref{recurrence}). \begin{claim} \label{cl} For a positive integer $n \geq 2$, we have $s_2(P_n) \geq 2 s_2(P_{n-2})$, and the equality holds only for $n=2,4,5$. \end{claim} \begin{proof} Since $s_2 (P_k) = k$ for $1 \leq k \leq 4$ and $s_2(P_5) = 6 = 2s_2 (P_3)$, it is easy to check that the equality holds for $n=2,4,5$. For $n\geq 6$, the recurrence relation (\ref{recurrence}) implies that \begin{align*} s_2(P_n) &= s_2(P_{n-1})+ s_2(P_{n-3}) = s_2(P_{n-2})+ s_2(P_{n-3})+ s_2(P_{n-4}) \\ &> s_2(P_{n-2})+ s_2(P_{n-3})+ s_2(P_{n-5})\\ &= s_2(P_{n-2})+s_2(P_{n-2}) = 2s_2(P_{n-2}).\qedhere \end{align*} \end{proof} Now we are ready to prove the main theorem of this section. \begin{theorem} For a tree $T$ of order $n$, we have $$ s_2(T) \leq s_2(P_n)$$ and the equality holds only for $T=P_n$ or $T=K_{1,3}$. \end{theorem} \begin{proof} We use induction on $n$. For the base case, we check all the trees with at most $4$ vertices, and conclude that $P_1, P_2, P_3, P_4$ and $K_{1,3}$ are all possible trees and all of them have only $2$-matchings of sizes at most one. Assume $n\geq 5$ and the theorem holds for all trees with at most $n-1$ vertices. Among all $n$-vertex trees $T$ which are not paths, we choose one maximizing the number of $2$-matchings and subject to that, we choose one minimizing the number of leaves. Note that $T$ has at least three leaves since it is not a path. If $T$ has diameter at most three, then the theorem holds by Observation \ref{observation}. So we suppose that $T$ is not a star and a double star. Let $T_0$ be a minimal subtree of $T$ containing all vertices of degree at least three, and $v$ be a leaf of $T_0$. Then $T-v$ has $j \geq 2$ path-components and at most one component which is not a path. Let $P_1,\dots, P_j$ be all those path-components of $T-v$ such that $P_i= v^i_1\dots v^i_{p_i}$ and $p_1\geq \dots \geq p_j$ and $v^i_1$ is adjacent to $v$ for $i \in [j]$. By Lemma \ref{lem}, one of the following three cases holds.\\ \noindent {\bf {Case 1.}} $p_1\geq 3$.\\ In this case, $v^{1}_{p_1}$ is a leaf and both $v^1_{p_1-2}$ and $v^1_{p_1-1}$ has degree two in $T$. Thus both $T - v^{1}_{p_1}$ and $T-v^1_{p_1-2} -v^1_{p_1-1}-v^1_{p_1}$ are trees with less than $n$ vertices. Especially, $T-v^1_{p_1}$ is not a path nor $K_{1,3}$. For any $r$-matching $M$ of $T$, if $M$ does not contain the edge $v^1_{p_1 - 1} v^1_{p_1}$, then it is an $r$-matching of $T-v^{1}_{p_1}$. If $M$ contains the edge $v^1_{p_1 - 1} v^1_{p_1}$, then $M-v^1_{p_1 - 1} v^1_{p_1}$ is an $2$-matching of $T-v^1_{p_1-2} -v^1_{p_1-1}-v^1_{p_1}$. This together with the induction hypothesis, we have \begin{align*} s_2( T) & = s_2( T-v^1_{p_1}) + s_2( T-v^1_{p_1-2} -v^1_{p_1-1}-v^1_{p_1}) < s_2(P_{n-1}) + s_2(P_{n-3})= s_2( P_{n}). \end{align*} by the recurrence relation~(\ref{recurrence}). Here we get the strict inequality since $T-v^1_{p_1}$ is not a path nor $K_{1,3}$. \vspace{0.1cm} \noindent {\bf {Case 2.}} \emph{$p_1\leq 2$ and $p_i+p_{i'}\geq 4$ for $ i\neq i' \in [j]$}.\\ In this case we have $p_1=\cdots=p_j=2$. Let $L:=\{v,v_1^1, v_2^1,\dots, v_1^j, v_2^j\}.$ For each $i\in [j]$, $v^{i}_2$ is a leaf and $v^{i}_1$ has degree two and $d_{T}(v) = j+1$. Thus both $T- v^1_2$ and $T-L$ are trees with less than $n$ vertices. For any $r$-matching $M$ of $T$, if $M$ does not contain the edge $v^1_{1} v^1_{2}$, then it is an $r$-matching of $T-v^{1}_{2}$. If $M$ contains the edge $v^1_{1} v^1_{2}$, then $M-v^1_{1} v^1_{2}$ is an $r$-matching of $T-v-v_1^1 -v_2^1$. The forest $T-v- v_1^1 - v_2^1$ is the disjoint union of $(j-1)$ copies of $K_2$ and $T-L$. By Observation~\ref{union} and the fact that $s_2(K_2)=2$, we have \begin{align*}\label{eq: s2T 222} s_2( T) = s_2( T-v^1_2) + s_2(T-v-v^1_1 -v^1_2) = s_2(T-v^1_2) + 2^{j-1}s_2( T-L). \end{align*} Since $T-v^1_2$ contains a vertex $v$ of degree at least three and a vertex $v^2_1$ of degree two, it is not a path or $K_{1,3}$. Thus the induction hypothesis gives us that $s_2( T-v^1_2) s_2(T)$. \end{proof} \section{The number of $r$-matchings in a tree} \label{big r} In this section, we estimate the maximum number of $r$-matchings in a tree $T$ of fixed order. For a fixed integer $r\geq 2$, let $s = s(r)$ be a positive real number such that $$r/2+s = (s+1)\log(s+1).$$ Note that by taking a logarithm and then taking derivative of the following function $f(x)$, it is easy to check that $f(x)$ satisfies the following. \begin{equation*}%\label{eq: property of s} \begin{minipage}[c]{0.8\textwidth}\em $f(x)=(x+1)^{\frac{1}{r/2+x}}$ has its maximum value at $x=s$. \end{minipage} \end{equation*} We investigate some properties of $s=s(r)$ for $r \geq 2$. First of all, we have $r>s$ since $r/2 + x < (x+1) \log (x+1)$ for all $x \geq r \geq 2$. We also get $s \geq e-1$ because $(s+1) \log (s+1) = s + \frac{r}{2} \geq s+1$. Since $h(x) = (x+1) \log (x+1) - x$ is increasing for $x > 1$, $s=s(r)$ is an increasing function on $r$ for $r \geq 2$ as $s$ is a solution of $h(x) = r/2$. In particular, $s$ satisfies the following. \begin{align}\label{eq: property of s 2} s = (1+o(1))\frac{r}{2\log{r}} \enspace \text{ and } \enspace s > \frac{r}{2 \log(r+1)} \text{ for all } r\geq 2, \end{align} To see this, note that $\log(r+1) \leq \log(\frac{3r}{2}) < \log(\frac{r}{2} + s) + \log{3} \leq \log(s+1) + \log\log(s+1) + \log{3}$. Hence \begin{eqnarray*} s &=& \frac{(s+1)\log(s+1) - \log(s+1)}{\log(s+1)} = \frac{r/2+s - \log(s+1)}{\log(s+1) } \geq \frac{r/2+s - \log(s+1)}{\log(r+1) } \\ &>& \frac{r}{2 \log(r+1)} > \frac{(s+1)\log(s+1) - s}{\log(s+1) + \log\log(s+1) + \log{3}} = s(1-o(1)) \end{eqnarray*} Finally, let $\alpha_r = f(s(r)) = (s+1)^{\frac{1}{r/2 + s}} = \exp(\frac{1}{s+1})$ which is the maximum value of $f(x)$. We prove some inequalities of $\alpha_r$, which is used in the proof of Theorem~\ref{main}. \begin{claim} \label{computation 1} $(e^{\frac{1}{r}}\alpha_r)^{r/2+s/2+1} \geq (e^{\frac{1}{r}}\alpha_r)^{r/2+s/2}+1 $ \end{claim} \begin{proof}Consider the following. \begin{align*} (e^{\frac{1}{r}}\alpha_r)^{r/2+s/2+1}-(e^{\frac{1}{r}}\alpha_r)^{r/2+s/2} &= (e^{\frac{1}{r}}\alpha_r -1)e^{\frac{r/2+s/2}{r}}\alpha_r^{r/2+s-s/2} \\ &= (e^{\frac{1}{r}}e^{\frac{1}{s+1}} -1)e^{\frac{r/2+s/2}{r}}(s+1)e^{-\frac{s/2}{s+1}} \\ &\geq \left(\frac{1}{s+1}+\frac{1}{r}\right)(s+1)e^{\frac{r/2+s/2}{r} - \frac{s/2}{s+1}}\\ & =\left(1+ \frac{s+1}{r}\right) e^{\frac{1}{2(s+1)}}e^{\frac{s}{2r}} \geq 1. \end{align*} Here, we use the fact that $e^{x}\geq 1+x$ for $x \in \mathbb{R}$. This proves the claim. \end{proof} \begin{claim} \label{computation 2} For an integer $w$ with $1\leq w \leq s+2$, we have $$(e^{\frac{1}{r}}\alpha_r)^{r+w}\geq (e^{\frac{1}{r}}\alpha_r)^{r+w-1}+w.$$ \end{claim} \begin{proof} Let $w=a(s+2)$ with $0\leq a\leq 1$. \begin{align*} (e^{\frac{1}{r}}\alpha_r)^{r+w}-(e^{\frac{1}{r}}\alpha_r)^{r+w-1} &= (e^{\frac{1}{r}}(s+1)^{\frac{1}{r/2+s}})^{r+w-1}(e^{\frac{1}{r}}(s+1)^{\frac{1}{r/2+s}}-1) \\ &= e^{1+\frac{w-1}{r}}(s+1)^{2+\frac{w-2s-1}{(s+1)\log(s+1)}}(e^{\frac{1}{r}}e^{\frac{1}{(s+1)}}-1) \\ &\geq e^{1}(s+1)^2 e^{\frac{w-2s-1}{s+1}}\left( \frac{1}{s+1}+\frac{1}{r}\right)\\ &= e^{1+\frac{w-2s-1}{s+1}}\left(s+1 + \frac{(s+1)^2}{r}\right) \\ &\geq e^{a-1 + \frac{a+1}{s+1}}(s+1) \geq \left(a+ \frac{a+1}{s+1}\right)(s+1) \geq a(s+2) \geq w. \end{align*} where the first inequality in the final line follows from $1+ \frac{a(s+2)-2s-1}{s+1} = a-1 + \frac{a+1}{s+1}$. This proves the claim.\end{proof} The following theorem gives an upper bound of $s_r (T)$ for an $n$-vertex tree $T$ and $r\geq 2$. \begin{theorem} \label{main} For an integer $r\geq 2$ and an $n$-vertex tree $T$, $$s_r( T) \leq (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-1}.$$ \end{theorem} \begin{proof}{ We use induction on $n$. If $T$ has diameter at most $r+1$, then $s_r (T) = n$ by Observation~\ref{observation}. Since \begin{align}\label{eq: base case n leq} n \leq (s+1)\left(1+ \frac{n-1}{r}+ \frac{n-1}{s+1}\right) \leq (s+1)(e^{\frac{1}{r}} e^{\frac{1}{s+1}})^{n-1} = (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-1}, \end{align} we conclude that the theorem holds for the trees of diameter at most $r+1$. In particular, the theorem is true for $n \leq r+2$. Now we assume that $n \geq r+3$, and the theorem holds for trees of order less than $n$. %We also assume that there is an $n$-vertex tree $T$ with $s_r(T) > (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-1}$. Among all $n$-vertex trees, we choose one with the maximum number of $r$-matchings, and subject to that, we choose one with the minimum number of leaves. Let $T$ be the chosen tree. We may assume that $T$ has diameter at least $r+2$, otherwise we are done by \eqref{eq: base case n leq}. If $T$ is a path, then let $P:= v_1v_2\cdots v_p$ with $p\geq r+3$, then we have the following Case 1. Otherwise let $T_0$ be a minimal subtree of $T$ containing all vertices of degree at least three, and let $u$ be a leaf of $T_0$. Since $u$ is a leaf of $T_0$, $T-u$ consists of at least three components and at most one of them is not a path. Let $P_1= v_1\ldots v_p$ and $P_2 = u_1\ldots u_q$ be two components of $T-u$ such that both $P_1$ and $P_2$ are paths, both $v_p$ and $u_q$ are adjacent to $u$, and both $v_1$ and $u_1$ are leaves in $T$. Without loss of generality we may assume $p \geq q$. By Lemma \ref{lem}, we have either $p\geq r+1$, $p+q>r+1$, or there exists an $n$-vertex tree $T'$ such that $s_r(T') \geq s_r(T)$ and the number of leaves of $T'$ is less than the number of leaves of $T$. The choice of $T$ implies that the third case does not occur. For the rest of the cases, we have $p+q >r+1$. Let $$L_1:= \{v_1,v_2,\cdots,v_{\min\{p,r+1\}}\}.$$ \\ \noindent {\bf Case 1. } \emph{$T$ is a path or $p \geq r/2 + s/2+1$}. \\ Note that both $T-v_1$ and $T-L_1$ are trees since $d_T(v_1)=1$ and $d_{T}(v_i)=2$ for all $2\leq i\leq p$. Consider an $r$-matching $M$ of $T$. If $M$ contains $v_1 v_2$, then $M- v_1v_2$ is an $r$-matching of $T- L_1$. If $M$ does not contain $v_1 v_2$, then $M$ is an $r$-matching of $T - v_1$. Thus the induction hypothesis and the fact that $|L_1| \geq p$ implies that \begin{align*} s_r(T) \leq s_r(T - L_1) + s_r(T- v_1) \leq (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-1-p} + (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-2}. \end{align*} This together with Claim \ref{computation 1} and the fact that $p\geq r/2+s/2+1$, we have $$s_r(T)\leq (s+1)((e^{\frac{1}{r}}\alpha_r)^{n-2}+(e^{\frac{1}{r}}\alpha_r)^{n-r/2-s/2-2}) \leq (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-1}.$$ \vspace{0.3cm} \noindent {\bf Case 2.} ${q\leq p < r/2+s/2 + 1}$.\\ In this case we have $L_1= \{v_1,v_2,\cdots,v_{p}\}$. Let $w:=p+q-r$, then we have $w = p+q-r < 2(r/2+s/2+1)-r = s+2.$ Let $$L_2 = \{ u u_q, u_{q}u_{q-1} \cdots, u_{w+1}u_{w}\}.$$ Here $p+q\geq r+2$, thus $w\geq 2$. Hence, we have that $u_1u_2 \notin L_2$. Let $F$ be a forest obtained from $T$ by deleting all vertices in $L_1$ and edges in $L_2$, and removing all isolated vertices. Then $F$ contains exactly two components, i.e. the component containing $u_1$, say $T_1$, and the component $T_2$ which does not contain $u_2$ but contains $u$ Then $T_1$ is a $w$-vertex subpath $u_1\dots u_{w}$ of $P_2$, and $T_2= T-V(P_1)-V(P_2)$ is a tree containing $n-p-q= n-(w+r)$ vertices. Since $T_1$ is a $w$-vertex path with $w < s+2 \leq r+2$, we have \begin{align}\label{eq: T1 and T2} s_r(T_1) \leq w. \end{align} Since $v_1$ is a leaf of $T$, $T-v_1$ is a tree. Thus the induction hypothesis implies that the number of all $r$-matchings in $T$ not containing $v_1v_2$ is at most \begin{align}\label{eq: sr T-v1} s_r( T-v_1) \leq (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-2}. \end{align} Note that any edge incident to $L_1$ is at distance at most $r-1$ from $v_1v_2$ and any edge in $L_2$ is also at distance at most $r-1$ from $v_1v_2$ by the definition of $w$. Thus for an $r$-matching $M$ containing $v_1v_2$ in $T$, the edge set $M-v_1v_2$ is also an $r$-matching in the forest $F$. Thus, the number of all $r$-matchings in $T$ containing $v_1v_2$ is at most $s_r(F)$. By Observation~\ref{union}, we have $$s_r(F) = s_r( T_1) s_r(T_2).$$ Thus by \eqref{eq: T1 and T2} and the induction hypothesis, the number of $r$-matchings in $T$ containing $v_1v_2$ is at most $$s_r(F) = s_r(T_1) s_r(T_2) \leq w (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-w+r-1}.$$ This together with \eqref{eq: sr T-v1} implies that \begin{eqnarray*} s_r(T)&=& s_r(T-v_1) + s_r(F) \\ &\leq& (s+1)((e^{\frac{1}{r}}\alpha_r)^{n-2} + w(e^{\frac{1}{r}}\alpha_r)^{n-r-w-1}) \\ &\leq& (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-r-w-1} ((e^{\frac{1}{r}}\alpha_r)^{r+w-1} + w) \\ &\leq & (s+1)(e^{\frac{1}{r}}\alpha_r)^{n-1}. \end{eqnarray*} where the last inequality follows from Claim~\ref{computation 2} with the fact that $1\leq w < s+2$. This completes the proof. }\end{proof} Now we estimate a lower bound of $\displaystyle \max_{T\in \mathbf{T}_{n}}s_r(T)$, which is not too far from the upper bound for sufficiently large $r$. \begin{theorem} \label{const} For $r\geq 2$ and $n\in \mathbb{N}$, there exists an $n$-vertex tree $T$ with $s_r(T) > \frac{1}{s+1}(e^{-6 \log (r+1)/r^2}\alpha_r)^{n-1}$. \end{theorem} \begin{proof} Let $t:=\lceil r/2+s+1/2\rceil$ and let $n':= t \lfloor (n-1)/t\rfloor+1$. Then $n'-1$ is a multiple of $t$. First, since $r/2\leq t$ and $t \leq (s+1)\log(s+1) +1$, we have \begin{align}\label{eq: t not big} (e^{-6 \log (r+1)/r^2}\alpha_r)^{t-1} \leq e^{-3 \log (r+1)/r} (s+1) \leq s+1. \end{align} We take a copy of $K_{1,\frac{n'-1}{t}}$ and subdivide each edges exactly $t-1$ times to obtain an $n'$-vertex tree $T'$ with $\frac{n'-1}{t}$ leaves. We consider the forest $F$ obtained from $T'$ by deleting all vertices with distance at most $(r-1)/2$ from the vertex of degree $\frac{n'-1}{t}$. Then $F$ is the disjoint union of $(n'-1)/t$ paths of $ t - \lceil r/2 \rceil +1$ vertices. Note that if $e,e'\in E(F)$ belong to two different components of $F$, then $\dist_{T'}(e,e')\geq r$. This implies that any $r$-matching in $F$ is also an $r$-matching in $T'$, thus $s_r (T') \geq s_r (F)$. Since the number of $r$-matchings in each path in $F$ is $s_r(P_{t - \lceil r/2 \rceil +1}) \geq t - \lceil r/2 \rceil +1 \geq \lceil s+1 \rceil$, the number of $r$-matchings in $F$ is at least \begin{align*} s_r (T') \geq s_r(F) &= \prod_{i=1}^{(n'-1)/t} s_r( P_{t- \lceil r/2 \rceil +1 }) \geq (\lceil s+1\rceil )^{\frac{n'-1}{t}}\geq (s+1)^{\frac{n'-1}{r/2+s}}(s+1)^{\frac{n'-1}{t}-\frac{n'-1}{r/2+s}} \\ &\geq \alpha_r^{n'-1}(s+1)^{-\frac{3(n'-1)}{2(r/2+s)^2} } \geq \alpha_r ^{n'-1} e^{-\frac{3(n'-1)}{2(r/2+s)(s+1)}} > (e^{-\frac{6 \log (r+1)}{r^2}}\alpha_r)^{n'-1}. \end{align*} where the last inequality follows by $\frac{3}{2(r/2+s)(s+1)} < \frac{3}{rs} \stackrel{\eqref{eq: property of s 2}}{<} \frac{6\log(r+1)}{r^2} $. Since there exists an $n$-vertex tree $T$ which contains $T'$ as a subtree, there exists an $n$-vertex tree $T$ with \begin{eqnarray*} s_r(T) &\geq& s_r(T') \geq (e^{-6 \log (r+1)/r^2}\alpha_r)^{n'-1} \geq (e^{-6 \log (r+1)/r^2}\alpha_r)^{n-1} (e^{-6 \log (r+1)/r^2}\alpha_r)^{-t+1} \\ &\stackrel{\eqref{eq: t not big}}{\geq}& \frac{1}{s+1}(e^{-6 \log (r+1)/r^2}\alpha_r)^{n-1}. \end{eqnarray*} \end{proof} %In fact, we can slightly extend Theorem~\ref{const} to every sufficiently large $n$; for every integer $r \geq 2$, there exists $n_0 = n_0(r)$ such that for every integer $n \geq n_0$, there is an $n$-vertex tree $T$ with $s_r(T) > (e^{-6 \log (r+1)/r^2}\alpha_r)^{n-1}$. We prove this in Appendix, as we need some tedious calculations. Note that the ratio between the upper bound from Theorem \ref{main} and the lower bound from Theorem \ref{const} is at most $(s+1)^2 e^{\left(\frac{1}{r} +\frac{6 \log (r+1)}{r^2}\right)(n-1)} = e^{ \frac{1+o(1)}{r}(n-1)}= \alpha_r^{\frac{1+o(1)}{2\log r}(n-1)}$. For sufficiently large $r$, there are $n$-vertex trees having more $r$-matchings than an $n$-vertex path for infinitely many $n$'s. To see this, note that we have $\alpha_r = \exp\left(\frac{1}{s+1}\right) = \exp\left((1+o(1)) \frac{2 \log r}{r}\right)$. By Theorem~\ref{lem:lemma1}, we have $\beta_r = \exp\left((1+o(1))\frac{\log r}{r}\right)$ and the number of $r$-matchings in the $n$-vertex path is $$(C_r+o(1))\beta_r^{n-1} = (C_r+o(1)) \alpha_r^{\left(\frac{1}{2}+o(1)\right)(n-1)}.$$ Theorem \ref{const} implies that there are $n$-vertex trees having more $r$-matchings than the $n$-vertex path for sufficiently large $r$ and infinitely many $n$'s. To analyze this further, let $T_{a,b}$ be the subdivided star obtained from $K_{1,b}$ by subdividing each edge $a-1$ times. In Section~\ref{sec: appendix}, we show that for some positive integer $a = a(r)$ and every integer $n \geq 2$ such that $n-1$ is divisible by $a$, $$\beta_r < s_r(T_{a,(n-1)/a})^{\frac{1}{n-1}}$$ for all $r \notin \{1,2,3,4,5,7,9\}$, implying that there are $n$-vertex trees with more $r$-matchings than $P_n$ for $r\notin\{1,2,3,4,5,7,9\}$ and infinitely many $n$'s. For $r=1,2$, such trees do not exist, and we do not know for $r \in \{3,4,5,7,9\}$. It would be interesting if one can identify the exact value at which such trees exist. \begin{problem}\label{prob} For each $r\in \{3,4,5,7,9\}$, determine whether the following holds. $$\max_{T_n\in \mathbf{T}_n} s_r(T_n) = s_r(P_n)$$ \end{problem} \section{Computations}\label{sec: appendix} Let $T_{a,b}$ be the subdivided star obtained from $K_{1,b}$ by subdividing each edge $a-1$ times. We show that for $r\in \mathbb{N}\setminus \{1,2,3,4,5,7,9\}$ and some integer $a = a(r)$, $$s_r(P_n) < s_r(T_{a,(n-1)/a}).$$ for every integer $n \geq 2$ such that $n-1$ is divisible by $a$. Recall that $s$ is a positive real number satisfying $r/2+s = (s+1)\log(s+1)$ and $p_r(x)= x^{r+1}-x^{r}-1$ and $\beta_r$ is the largest real roots of $p_r(x)=0$. In the following table, we indicate the actual example constructed in the same way as in the proof of Theorem \ref{const} with more precise choice of parameter $a$, rather than $t$ in the proof of Theorem~\ref{const}. \begin{center} \begin{tabular}{c||c|c|c|c|c} $r$ & $s$ & $\alpha_r$ & $\beta_r$ & $a$ & $s_r(T_{a,(n-1)/a})^{\frac{1}{n-1}}$ \\ \hline 2 & $1.7182\ldots$ & $1.4446\ldots$ & $1.4655\ldots$ & 3 & $ \geq3^{1/3}=1.4422\ldots$ \\ 3 & $2.1809\ldots$ & $1.3693\ldots$ & $1.3802\ldots$ & 5 & $ \geq4^{1/5}=1.3195\ldots$ \\ 4 & $2.5911\ldots$ & $1.3210\ldots$ & $1.3247\ldots$ & 5 & $ \geq4^{1/5}=1.3195\ldots$ \\ 5 & $2.9673\ldots$ & $1.2866\ldots$ & $1.2852\ldots$ & 6 & $ \geq4^{1/6} = 1.2599\ldots$ \\ 6 & $3.3191\ldots$ & $1.2605\ldots$ & $1.2554\ldots$ & 6 & $ \geq4^{1/6} = 1.2599\ldots$ \\ 7 & $3.6523\ldots$ & $1.2397\ldots$ & $1.2320\ldots$ & 8 & $ \geq5^{1/8} = 1.2228\ldots$ \\ 8 & $3.9706\ldots$ & $1.2228\ldots$ & $1.2131\ldots$ & 8 & $ \geq5^{1/8} = 1.2228\ldots$ \\ 9 & $4.2766\ldots$ & $1.2086\ldots$ & $1.1974\ldots$ & 10 & $ \geq6^{1/10} = 1.1962\ldots$ \\ 10 & $4.5723\ldots$ & $1.1965\ldots$ & $1.1842\ldots$ & 10 & $ \geq6^{1/10} = 1.1962\ldots$\\ 11 & $4.8592\ldots$ & $1.1861\ldots$ & $1.1729\ldots$ & 11 & $ \geq6^{1/11} = 1.1769\ldots$\\ 12 & $5.1383\ldots$ & $1.1769\ldots$ & $1.1631\ldots$ & 11 & $ \geq6^{1/11} = 1.1769\ldots$\\ 13 & $5.4106\ldots$ & $1.1688\ldots$ & $1.1544\ldots$ & 13 & $ \geq7^{1/13} = 1.1614\ldots$ \\ 14 & $5.6767\ldots$ & $1.1615\ldots$ & $1.1468\ldots$ & 13 & $ \geq7^{1/13} = 1.1614\ldots$ \\ 15 & $5.9374\ldots$ & $1.1550\ldots$ & $1.1400\ldots$ & 14 & $ \geq7^{1/14} = 1.1491\ldots$ \\ 16 & $6.1932\ldots$ & $1.1491\ldots$ & $1.1339\ldots$ & 14 & $ \geq7^{1/14} = 1.1491\ldots$ \\ 17 & $6.4444\ldots$ & $1.1437\ldots$ & $1.1283\ldots$ & 16 & $ \geq8^{1/16} = 1.1387\ldots$ \\ 18 & $6.6914\ldots$ & $1.1388\ldots$ & $1.1233\ldots$ & 16 & $ \geq8^{1/16} = 1.1387\ldots$ \\ 19 & $6.9346\ldots$ & $1.1343\ldots$ & $1.1187\ldots$ & 17 & $ \geq8^{1/17} = 1.1301\ldots$ \\ 20 & $7.1743\ldots$ & $1.1301\ldots$ & $1.1144\ldots$ & 17 & $ \geq8^{1/17} = 1.1301\ldots$ \\ 21 & $7.4107\ldots$ & $1.1262\ldots$ & $1.1105\ldots$ & 19 & $ \geq9^{1/19} = 1.1225\ldots$ \\ 22 & $7.6440\ldots$ & $1.1226\ldots$ & $1.1069\ldots$ & 19 & $ \geq9^{1/19} = 1.1225\ldots$ \\ 23 & $7.8744\ldots$ & $1.1192\ldots$ & $1.1036\ldots$ & 20 & $ \geq9^{1/20} = 1.1161\ldots$ \\ 24 & $8.1021\ldots$ & $1.1161\ldots$ & $1.1004\ldots$ & 20 & $ \geq9^{1/20} = 1.1161\ldots$ \\ 25 & $8.3272\ldots$ & $1.1131\ldots$ & $1.0975\ldots$ & 22 & $ \geq10^{1/22} = 1.1103\ldots$ \\ \end{tabular} \end{center} For $r\geq 25$, it is easy to check $r/2 - s > 4$ since $r/2 - s = (s+1) \log (s+1)-2s$ is an increasing function on $s$ for $s>e-1$ and $s(r)$ is also an increasing function on $r$. Thus we have \begin{align}\label{eq: r-3 geq r+s/2} r-4 \geq r/2+s = (s+1)\log(s+1). \end{align} The proof of Theorem~\ref{const} shows that for all $r\geq 2$, $t = \lceil r/2 + s + 1/2 \rceil$ and integer $n \geq 2$ such that $n-1$ is divisible by $t$, we have $$s_r(T_{t,(n-1)/t})^{\frac{1}{n-1}} \geq \alpha_r e^{-\frac{3}{2(r/2+s)(s+1)}}.$$ We claim that $\alpha_r e^{-\frac{3}{2(r/2+s)(s+1)}} > \beta_r$ for $r \geq 25$. Since $\beta_r$ is a root of $p_r(x)$ in $(1, \infty)$ and $p_r(x)$ is an increasing function for $x>1$, it is enough to show that $p_r( \alpha_r e^{-\frac{3}{2(r/2+s)(s+1)}}) > 0$. Indeed, since $\alpha_r = e^{1/(s+1)}$ we have \begin{eqnarray*} p_r\left( \alpha_r e^{-\frac{3}{2(r/2+s)(s+1)}}\right) &=& e^{\frac{r+1}{s+1} - \frac{3(r+1)}{2(r/2+s)(s+1)}} - e^{\frac{r}{s+1}-\frac{3r}{2(r/2+s)(s+1)}} - 1 \\ &\geq & e^{\frac{r}{s+1}-\frac{3r}{2(r/2+s)(s+1)}} \left( e^{\frac{1}{s+1} - \frac{3}{2(r/2+s)(s+1)} } -1 \right) -1 \\ &\geq & e^{\frac{r-3}{s+1}} \left( e^{\frac{1}{s+1} - \frac{3}{2(r/2+s)(s+1)} } -1 \right) -1 \\ &\geq &e^{\frac{1}{s+1}} e^{\frac{r-4}{s+1}}\left(\frac{1}{s+1} - \frac{3}{2(r/2+s)(s+1)} \right) -1 \\ &\stackrel{\eqref{eq: r-3 geq r+s/2}}{\geq }& e^{\frac{1}{s+1}} e^{\log(s+1)}\left(\frac{1}{s+1} - \frac{3}{2(s+1)^2 \log(s+1)} \right) -1 \\ &= & (1 + \frac{1}{s+1})\left( 1 - \frac{3}{2(s+1)\log(s+1)}\right) - 1\\ & \geq & \frac{1}{s+1} - \frac{3}{2(s+1)\log(s+1)} - \frac{3}{2(s+1)^2\log(s+1)} \\ \\ &>& 0 \end{eqnarray*} We get the final inequality since $s\geq 8$ for $r\geq 25$. This shows that $s_r(T_{t,(n-1)/t})^{\frac{1}{n-1}} \geq \alpha_r e^{-\frac{3}{2(r/2+s)(s+1)}} > \beta_r$ for all $r\geq 25$ and every integer $n \geq 2$ such that $n-1$ is divisible by $t$. This with the table above shows that for $r\in \mathbb{N}\setminus \{1,2,3,4,5,7,9\}$ and some integer $a = a(r)$, we have $$s_r(P_n) < s_r(T_{a,(n-1)/a})$$ for every large enough integer $n$ for which $n-1$ is divisible by $a$. In particular, for $r\in \mathbb{N}\setminus \{1,2,3,4,5,7,9\}$, there are $n$-vertex trees $T_n$ with $s_r(P_n) < s_r (T_n)$ for infinitely many $n$'s. \begin{thebibliography}{99} \bibitem{A91} N.~Alon. \newblock Independent sets in regular graphs and sum-free subsets of finite groups. \newblock {\em Israel J. Math.}, 73: 247--256, 1991. \bibitem{BET80} R.~Baxter, I.~Enting and S.~Tsang. \newblock Hard-square lattice gas. \newblock {\em J. Statist. Phys.}, 22 (4): 465--489, 1980. \bibitem{B73} L.~Br\'egman. \newblock Some properties of nonnegative matrices and their permanents. \newblock {\em Soviet Math. Dokl.}, 15: 945--949, 1973. \bibitem{C14} P.~Csikv\'{a}ri. \newblock Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems. \newblock \arxiv{1406.0766}, 2014. \bibitem{CR14} J.~Cutler and A.~Radcliffe. \newblock The maximum number of complete subgraphs in a graph with given maximum degree. \newblock {\em J. Combin. Theory Ser. B}, 104: 60--71, 2014. \bibitem{G77} I.~Gutman. \newblock Acyclic systems with extremal H\''{u}ckel $\pi$--electron energy. \newblock {\em Theor. Chim. Acta}, 45:79--87, 1977. \bibitem{GP86} I.~Gutman and O.~Polanskym. \newblock Mathematical concepts in organic chemistry. \newblock {\em Springer-Verlag, Berlin}, 1986. \bibitem{HL72} O.~Heilmann and E.~Lieb. \newblock Theory of monomer-dimer systems. \newblock {\em Comm. Math. Phys.}, 25: 190--232, 1972. \bibitem{H86} H.~Hosoya. \newblock Topological index as a common tool for quantum chemistry, statistical mechanics, and graph theory. \newblock {\em Ellis Horwood Ser. Math. Appl.} 110--123. Horwood, Chichester, 1986. \bibitem{Law12} H.-F.~Law. \newblock On the number of $F$-matchings in a tree. \newblock {\em Electron. J. Combin.}, 19 (2012), \#P43. \bibitem{K01} J.~Kahn. \newblock An entropy approach to the hard-core model on bipartite graphs. \newblock {\em Combin. Probab. Comput.}, 10: 219--237, 2001. \bibitem{KW80} D.~Kleitman and K.~Winston. \newblock The asymptotic number of lattices. \newblock {\em Ann. Discrete Math.}, 6: 243--249, 1980. \bibitem{KW82} D.~Kleitman and K.~Winston. \newblock On the number of graphs without 4-cycles. \newblock {\em Discrete Math.}, 41: 167--172, 1982. \bibitem{LLS01} V.~Lev, T.~\L{}uczak and T.~Schoen. \newblock Sum-free sets in abelian groups. \newblock {\em Israel J. Math.}, 125: 347--367, 2001. \bibitem{MS89} R.~Merrifield and H.~Simmons. \newblock Topological Methods in Chemistry. \newblock {\em Wiley, New York.}, 1989. \bibitem{M63} H.~Minc. \newblock Upper bounds for permanents of (0,1)-matrices. \newblock {\em Bull. Amer. Math. Soc.}, 69: 789--791, 1963. \bibitem{PT82} H.~Prodinger and R.F.~Tichy. \newblock Fibonacci numbers of graphs. \newblock {\em Fibonacci Quart.}, 20: 16--21, 1982. \bibitem{S01} A.~Sapozhenko. \newblock On the number of independent sets in extenders. \newblock {\em Diskret. Mat.}, 13: 56--62, 2001. \bibitem{SS05} A.D.~Scott and A.D.~Sokal. \newblock The repulsive lattice gas, the independent-set polynomial, and the Lov\'asz local lemma. \newblock {\em J. Stat. Phys.}, 118: 1151--1261, 2005. \bibitem{W07} S.~Wagner. \newblock On the number of matchings of a tree. \newblock {\em European J. Combin.}, 28: 1322-1330, 2007. \bibitem{WG10} S.~Wagner and I.~Gutman. \newblock Maxima and minima of the Hosoya index and the Merrifield-Simmons index: A survey of results and techniques. \newblock {\em Acta Appl. Math.}, 112: 323--346, 2010. %\bibitem{Wil86} H.~Wilf. \newblock The number of maximal independent sets in a tree, \newblock {\em SIAM J. Algebraic Discrete Methods}, 7: 125--130, 1986. \bibitem{Z10} Y.~Zhao. \newblock The Number of Independent Sets in a Regular Graph, \newblock {\em Combin. Probab. Comput.}, 19: 315--320, 2010. \end{thebibliography} \end{document}