# Trees maximizing the number of almost-perfect matchings

Stijn Cambie  Bradley McCoy  Gunjan Sharma  Stephan Wagner  Corrine Yap

###### Abstract

We characterize the extremal trees that maximize the number of almost-perfect
matchings, which are matchings covering all but one or two vertices, and those
that maximize the number of strong almost-perfect matchings, which are
matchings missing only one or two leaves. We also determine the trees that
minimize the number of maximal matchings. We apply these results to extremal
problems on the weighted Hosoya index for several choices of vertex-degree-
based weight function.

2020 Mathematics Subject Classification. Primary 05C05; Secondary 05C09,
05C70Keywords: trees, matching, almost-perfect matching, maximal matching,
weighted Hosoya index

##  1 Introduction

A matching in a graph $G$ is a set of edges such that no two edges share a
vertex. Matching theory has a rich history with many applications. In
particular, extremal problems and enumeration problems involving matchings
have been studied extensively. A maximum matching can be the best solution to
a variety of problems, such as scheduling and task assignment problems or
matching donors with receivers [2, 11].

Computing the number of matchings in a graph, also called the Hosoya index, is
#P-complete in general. In this paper, we focus on enumeration of matchings in
trees. It is known that the number of matchings in the path graph $P_{n}$ is
equal to $F_{n}$, the $n$th Fibonacci number, and that this is the maximum
over all $n$-vertex trees [5]. In fact, the star and the path respectively
minimize and maximize not only the number of matchings but also the number of
induced matchings [8], and the number of matchings of a fixed size [15, Thm.
4.7.3]. In the last case, we show that the path is, in fact, the unique
maximizer. For a more comprehensive background on matching enumeration
problems, see e.g. the survey of Wagner and Gutman [14], or the book by Wagner
and Wang [15].

To prove that the path uniquely maximizes the number of matchings of a fixed
size, we require results on almost-perfect matchings which are of independent
interest. Perfect matchings are central to the study of matching theory—Hall’s
matching theorem and Tutte’s theorem are perhaps the most notable examples [6,
13]. However, the notion of a matching that is “close to perfect” has been
less prevalent. When the number of vertices in a graph is odd, an almost-
perfect matching is a matching that avoids a single vertex. This is also
called a near-perfect matching, and enumeration problems for other classes of
graphs (such as factor-critical) have been considered [10]. When the number of
vertices is even, an almost-perfect matching avoids two vertices. We
characterize the extremal trees in both cases and prove the following:

######  Theorem 1.

If $n$ is odd, a tree $T$ of order $n$ has at most $\frac{n+1}{2}$ almost-
perfect matchings. Equality holds if and only if $T$ is a $1$-subdivision of a
tree of order $\frac{n+1}{2}.$

######  Theorem 2.

If $n$ is even, a tree $T$ of order $n$ has at most
$\binom{\frac{n}{2}+1}{2}=\frac{n(n+2)}{8}$ almost-perfect matchings.

  * •

For $n>4$, equality holds if and only if $T$ is the path $P_{n}$.

  * •

For $n=4$, equality holds for both $P_{4}$ and $S_{4}$.

We consider the same questions for strong almost-perfect matchings, which are
matchings that cover all vertices except one or two leaves, and again find
precise characterizations of the extremal graphs. When the order is odd, the
number of strong almost-perfect matchings is maximized by the basic spider (a
star with all but at most one edge subdivided once, as presented in Figure 1);
this is the same construction that, for example, maximizes the number of
maximal independent sets [16].

######  Theorem 3.

Let $T$ be a tree of order $n\geq 28$. Then the number of strong almost-
perfect matchings in $T$ is at most $\frac{n-1}{2}$ if $n$ is odd and
$\mathopen{}\left\lfloor\frac{(n-4)^{2}}{12}\right\rfloor\mathclose{}$ if $n$
is even. Equality holds if and only if $T$ is a spider (when $n$ is odd) or a
balanced spider-trio (when $n$ is even).

In fact, we are able to give a complete picture of the bounds and extremal
trees for all values of $n$, but postpone the precise statements until Section
3.

The trees that maximize the number of maximal matchings have been previously
determined by Górska and Skupień [4]. Surprisingly, the characterization of
the trees that minimize the number of maximal matchings has not appeared in
the literature. We show that the extremal trees are precisely the most basic
spiders again, or a special spider if $n$ is odd.

######  Theorem 4.

A tree $T$ of order $n$ has at least $\lceil\frac{n}{2}\rceil$ maximal
matchings. Equality holds if and only if $T$ is a spider
$\operatorname{Sp}_{n}$, or an odd special spider $\operatorname{SS}_{n}$.

In Section 5, we consider applications to the weighted Hosoya index
$Z_{\phi}(T)$, where each edge is assigned a weight by $\phi$ and the weight
of a matching is the product of its edge weights. Motivated by recent results
by Cruz, Gutman, and Rada [1], we consider certain choices of vertex-degree-
based weight functions and prove that while the minimizer is the star in all
cases that we consider, the maximizer can be the path, the double-broom, or a
type of spider.

The outline of the paper is as follows: in Section 2, we prove Theorems 1 and
2. In Section 3, we prove Theorem 3. In Section 4, we prove Theorem 4. In
Section 5, we prove results related to the weighted Hosoya index. We conclude
by discussing some further questions to pursue in Section 6.

###  1.1 Preliminaries

In this subsection, we introduce definitions and notation that will be used
throughout the paper. Given a graph $G=(V,E)$, a _matching_ $M$ in $G$ is a
set of edges such that no two edges share a common vertex. A matching is
_maximal_ if it is not a subset of any other matching. A matching is a
_maximum matching_ if it has the largest possible cardinality. A _perfect_
matching is a matching that includes all vertices.

The diameter of a graph $G$, denoted $diam(G)$, is the maximum distance
between any pair of vertices over all pairs in $G$. When we say “a diameter of
$G$,” we mean a path with length equal to $diam(G)$. A $1$-subdivision of an
edge $uv$ is obtained by adding a new vertex $x_{uv}$ and replacing $uv$ with
the path $\\{u,x_{uv},v\\}$. A $1$-subdivision of a graph is a graph all of
whose edges are ($1$-)subdivided.

######  Definition 5.

In a tree of order $n$, a matching $M$ is an almost-perfect matching (APM) if
it covers all but one vertex when $n$ is odd and all but two vertices when $n$
is even. The vertices not covered by $M$ are called the avoided vertices. $M$
is a strong almost-perfect matching (SAPM) if the avoided vertices are leaves.

Let $\mathcal{M}(G)$ be the set of all matchings of $G$, $\mathcal{M}_{k}(G)$
be the set of matchings in $G$ of size $k$, and
$m_{k}(G)=|\mathcal{M}_{k}(G)|$ with $m_{0}(G)=1$. The _Hosoya index_ of $G$
is the number of matchings of $G$, which can be written as

$Z(G)=|\mathcal{M}(G)|=\Sigma_{k\geq 0}m_{k}(G).$

The name of the index refers to Hosoya [7] who observed that if $G$ is a
molecular graph, the Hosoya index is correlated with its chemical properties.

Let $(G,\omega)$ denote a graph with weight function
$\omega:E\to\mathbb{R}^{+}$. The weight of a matching $M$ is then the product
of the weights of the edges in $M$, and the _weighted Hosoya index_ is

$Z(G,\omega)=\sum_{M\in\mathcal{M}}\left(\prod_{e\in M}\omega(e)\right)$

As an aside, observe that this coincides with the definition of the
(multivariate) monomer-dimer partition function from statistical physics when
$\omega(e)$ is a positive constant $\lambda_{e}$ for each edge $e$.

Let $e=uv$ with $\deg(u)=i$ and $\deg(v)=j$. The weight function is _vertex-
degree-based_ if $\omega(e)=\phi(i,j)$ where $\phi$ is a function such that
$\phi(i,j)=\phi(j,i)$. In this case, we denote $Z(G,\omega)$ by $Z_{\phi}(G).$

We finish this section with some statements that we will use in our proofs
throughout. We will refer to the fact $\sum_{v\in V(G)}\deg(v)=2|E(G)|$ as the
“handshaking lemma.” The following is also a well-known statement:

######  Lemma 6.

Every tree has at most one perfect matching.

###### Proof.

Suppose $M$ and $M^{\prime}$ are two perfect matchings of $T$. In the graph
$(V(T),M\cup M^{\prime})$, every component must be either a single edge
(contained in both $M$ and $M^{\prime}$) or a cycle. As $T$ is a tree, it
contains no cycles and so we must have $M=M^{\prime}$. ∎

A sequence $(x_{i})_{i=1}^{k}$ where $x_{1}\geq x_{2}\geq\cdots\geq x_{k}$
majorizes the sequence $(y_{i})_{i=1}^{k}$, $y_{1}\geq y_{2}\geq\cdots\geq
y_{k}$, if and only if $\sum_{i=1}^{j}x_{i}\geq\sum_{i=1}^{j}y_{i}$ for every
$1\leq j\leq k$ and equality holds for $j=k$.

Observe that an equivalent definition is the following: $(x_{i})_{i=1}^{k}$
where $x_{1}\leq x_{2}\leq\cdots\leq x_{k}$ majorizes $(y_{i})_{i=1}^{k}$,
$y_{1}\leq y_{2}\leq\cdots\leq y_{k}$, if and only if
$\sum_{i=1}^{j}x_{i}\leq\sum_{i=1}^{j}y_{i}$ for all $1\leq j\leq k$ with
equality when $j=k$.

######  Lemma 7 (Karamata’s inequality, [9]).

If $(x_{i})_{i=1}^{k}$ is a sequence of real numbers that majorizes
$(y_{i})_{i=1}^{k}$, and $f$ is a real-valued convex function, then
$\sum_{i=1}^{k}f(x_{i})\geq\sum_{i=1}^{k}f(y_{i})$. This inequality is strict
if the sequences are not equal and $f$ is a strictly convex function. If $f$
is concave, the reverse inequality holds.

##  2 Maximum number of matchings of a fixed size

In this section, we characterize the trees $T$ of order $n$ maximizing the
number of almost-perfect matchings and use this to characterize those
maximizing the number of matchings of a fixed size $k$. When $n=2k$, any tree
with a perfect matching is extremal since the perfect matching must be unique.
While it is straightforward to check if a given tree has a perfect matching,
there is not a clear characterization of the set of all trees with perfect
matchings (there are exponentially many of them [12]).

When $n=2k+1$, we prove that there are many extremal trees maximizing the
number of almost-perfect matchings. For convenience, we recall the theorem
statement:

######  Theorem 1.

If $n$ is odd, a tree $T$ of order $n$ has at most $\frac{n+1}{2}$ almost-
perfect matchings. Equality holds if and only if $T$ is a $1$-subdivision of a
tree of order $\frac{n+1}{2}.$

###### Proof.

Recall that every tree has a unique bipartition, so let $T=(X\cup Y,E)$. If
$T$ has an almost-perfect matching, then the bipartition classes must differ
by $1$ and the larger one, without loss of generality $X$, contains precisely
$\frac{n+1}{2}$ vertices. This immediately implies the upper bound, since
$T\setminus y$ for $y\in Y$ cannot have a perfect matching.

Next, we prove the characterization of the extremal trees. Let $T^{\prime}$ be
an arbitrary tree of order $\frac{n+1}{2}$. Let $T$ be a 1-subdivision of
$T^{\prime}$, with $Y$ the set of added vertices. For every $v\in
V(T^{\prime})$, we can construct a perfect matching of $T\setminus v$: viewing
$T$ as a tree rooted at $v$, match each $u\in V(T^{\prime})\setminus v$ with
its neighbor (in $Y$) on the unique path from $u$ to $v$. Hence any
subdivision of a tree of order $\frac{n+1}{2}$ contains $\frac{n+1}{2}$
almost-perfect matchings.

We prove the other direction by induction on $n$. The cases $n\in\\{1,3\\}$
are straightforward, since $P_{3}$ is the only tree of order $3$ and is the
$1$-subdivision of $P_{2}$. Thus, assume the statement is true for $n-2,$
where $n\geq 5$. Let $T=(X\cup Y,E)$ be a tree that attains equality and
without loss of generality, let $|X|=\frac{n+1}{2}$. Then for every choice of
$v\in X$, $T\setminus v$ has a perfect matching. Observe that every leaf of
$T$ must be in $X$. If there is a leaf in $Y$, then its unique neighbor in $X$
cannot be avoided by an almost-perfect matching, since any such matching would
also avoid the leaf itself. This implies that no two leaves can have the same
neighbor. Indeed, if $x_{1},x_{2}\in X$ are leaves, then for any $v\in X$ such
that $v\neq x_{1},x_{2}$, the almost-perfect matching that avoids $v$ would
have to cover both leaves $x_{1}$ and $x_{2}$, a contradiction.

Now let $x\in X$ be a leaf such that its unique neighbor $y$ has degree 2
(such a leaf must exist, e.g. one of the ends of a diameter). Then
$T^{\prime}:=T\setminus\\{x,y\\}$ is a tree. Furthermore, for any $v\in
X\setminus\\{x\\}$, we know that $T\setminus\\{v\\}$ has a perfect matching,
which must contain the edge $xy$. Thus, $T^{\prime}$ contains $\frac{n-1}{2}$
almost-perfect matchings so we may apply the inductive hypothesis to conclude
that $T^{\prime}$ is a $1$-subdivision of a tree, and hence $T$ is as well. ∎

Next, we will show that when $n=2k+2$, the path is extremal in all non-trivial
cases. We start with a lemma that will be applied in the proof of this and
some further theorems.

######  Lemma 8.

If $n$ is even and $T$ is a tree of order $n$ with at least one pair of leaves
sharing a common neighbor, then $T$ has at most $n-1$ almost-perfect
matchings.

###### Proof.

Recall that for $n$ even, an almost-perfect matching $M$ covers all but two
vertices, and we call these vertices the avoided pair of $M$. Let $T$ be a
tree of order $n$, and let $u$ and $u^{\prime}$ be the two leaves with a
common neighbor (siblings). No matching can cover both leaves, so for every
almost-perfect matching $M$ of $T$, at least one of $u$ and $u^{\prime}$ is
contained in the avoided pair of $M$.

By Theorem 1, $T\setminus u$ and $T\setminus u^{\prime}$ have both at most
$\frac{n}{2}$ almost-perfect matchings. Equality is only possible if
$T\setminus u$ and $T\setminus u^{\prime}$ are $1$-subdivisions of a tree.
Since the perfect matching of $T\setminus\\{u,u^{\prime}\\}$ has been counted
twice, $T$ has at most $n-1$ almost-perfect matchings. Because $T\setminus u$
and $T\setminus u^{\prime}$ are isomorphic, we also know that equality is
attained if and only if $T$ is a $1$-subdivision of a tree of order
$\frac{n}{2}$ where one copy of a leaf is added (i.e. a copy $u^{\prime}$ of a
leaf $u$ with the same neighbor). ∎

We use this to prove the case for $n$ even:

######  Theorem 2.

If $n$ is even, a tree $T$ of order $n$ has at most
$\binom{\frac{n}{2}+1}{2}=\frac{n(n+2)}{8}$ almost-perfect matchings.

  * •

For $n>4$, equality holds if and only if $T$ is the path $P_{n}$.

  * •

For $n=4$, equality holds for both $P_{4}$ and $S_{4}$.

###### Proof.

One can check by hand that for $n=4$ both $P_{4}$ and $S_{4}$ have three
almost-perfect matchings, for $n=6$ the path $P_{6}$ has eight almost-perfect
matchings, and in both cases these are the only examples attaining the
maximum.

Now let $n\geq 8$ and suppose the claim holds for all even numbers less than
or equal to $n-2$.

Since $n<\frac{n(n+2)}{8}$, by Lemma 8 we may assume there are no two leaves
with a common neighbor. Taking a diameter of the tree, we note that there is
an edge $uv$ with $u$ a leaf and $v$ its neighbor of degree $2$. Then either
$uv$ is contained in the almost-perfect matching, or the avoided pair contains
$u$. We count the number of matchings in each case and take the sum to get the
total number of almost-perfect matchings in $T$.

For the first term, the number of almost-perfect matchings containing $uv$ is
equal to the number of almost-perfect matchings in $T\setminus\\{u,v\\}$ which
by the inductive hypothesis is at most $\frac{n(n-2)}{8}$. For the second
term, the number of avoided pairs containing $u$ is at most the number of
almost-perfect matchings in $T\setminus u$, which is bounded by
$\frac{(n-1)+1}{2}$ by Theorem 1. Since
$\frac{n(n-2)}{8}+\frac{(n-1)+1}{2}=\frac{n(n+2)}{8}$, the first statement of
the theorem holds by induction.

To characterize equality, we see by the inductive hypothesis that equality
holds for the first term if and only if $T\setminus\\{u,v\\}=P_{n-2}$. By
Theorem 1, equality holds for the second term if and only if
$T\setminus\\{u\\}$ is a 1-subdivision of a tree of order $\frac{n}{2}$. Since
$v$ must have degree 2, these imply that equality holds overall if and only if
$T=P_{n}$. ∎

Another way of stating Theorem 2 is that $P_{n}$ maximizes $m_{k}(T)$ when
$n=2k+2$ and $k\geq 2$. We can extend this to larger values of $n$. Note that
$m_{1}(T)=n-1$ for every tree $T$ and so it has been omitted in the statement.

######  Theorem 9.

If $k\geq 2$ and $T$ is a tree of order $n$ with $n\geq 2k+2$, then
$m_{k}(T)\leq m_{k}(P_{n})=\binom{n-k}{k}$. Equality holds if and only if
$T=P_{n}.$

###### Proof.

We will prove that the statement is true for forests of order $n$ using
induction on $k$.

When $k=2$, for a tree $T$ we have
$m_{2}(T)=\binom{n-1}{2}-\sum_{v}\binom{\deg(v)}{2}.$ Observe that the degree
sequence of the path $P_{n}$ is majorized by the degree sequence of any other
$n$-vertex tree. Indeed, the degree sequence of $P_{n}$ is
$(2,2,\ldots,2,1,1)$. If $T\neq P_{n}$ has degree sequence $(d_{1}\geq
d_{2}\geq\cdots\geq d_{n})$ and $\sum_{i=1}^{j}d_{i}<2j$ for some $j\leq n-2$,
then we must have $d_{i}=1$ for all $i\geq j$. Then
$\sum_{i=1}^{n}d_{i}<2j+(n-j)\leq 2n-2$, a contradiction since
$\sum_{i=1}^{n}d_{i}=2(n-1)$ by the handshaking lemma. Thus, we may apply
Lemma 7 (with strict inequality since the degree sequences of $T$ and $P_{n}$
must be different) to conclude that for any $T\neq P_{n}$, we have
$m_{2}(T)<m_{2}(P_{n})={n-2\choose 2}$.

If $F$ is a forest with at least two components, then $|E(F)|\leq n-2$ and as
such, $m_{2}(F)\leq{n-2\choose 2}$. Equality is not possible when $n>4$.

Now assume the statement holds for $m_{k-1}(T)$ for any $T$ on $n\geq 2k$
vertices. When $n=2k+2$, a matching of size $k$ is an almost-perfect matching
and so $P_{n}$ is extremal among trees by Theorem 2. For a forest $F$ with
multiple components, there are three cases.

Case 1: All components of $F$ have even size. Let the components of $F$ be
$T_{1},T_{2},\dots,T_{r}$ where $|T_{i}|=2k_{i}$ for $1\leq i\leq r$. An
almost-perfect matching of $F$ consists of an almost-perfect matching of
$T_{i}$ for some $i$ and a perfect matching of $T_{j}$ for every $j\neq i$, of
which there is at most one by Lemma 6. Then

$m_{k}(F)\leq\sum_{i=1}^{r}m_{k_{i}-1}(T_{i})\leq\sum_{i}m_{k_{i}-1}(P_{2k_{i}})$

We claim this is strictly less than $m_{k}(P_{n})$. By Theorem 2, it suffices
to observe that

$\sum_{i=1}^{r}\binom{k_{i}+1}{2}<\binom{\sum k_{i}+1}{2}.$

This is true by induction on $r$ since
$\binom{a+b+1}{2}>\binom{a+1}{2}+\binom{b+1}{2}$ for every $a,b\geq 1$ (a
straightforward computation).

Case 2: At least four components are odd. Then $m_{k}(F)=0$ since at least one
vertex from each of the four components must be avoided.

Case 3: Exactly two components are odd, with order $a$ and $b$. In the last
case, we apply Theorem 1 and the inequality between the arithmetic and
geometric mean (AM-GM) to conclude
$m_{k}(F)\leq\frac{a+1}{2}\cdot\frac{b+1}{2}\leq\left(\frac{k+2}{2}\right)^{2}<\binom{k+2}{2}=m_{k}(P_{n}).$
Thus, the statement is true for forests when $n=2k+2.$

So for $n\geq 2k+3$, we may assume that the claim holds for $n-1$.

Let $F$ be a forest and $u$ a leaf of $F$, with unique neighbor $v$ (a forest
without edges is clearly not extremal). We observe that
$m_{k}(F)=m_{k}(F\setminus u)+m_{k-1}(F\setminus uv)$, since either $u$ is
covered by the matching or it is not. By the inductive hypothesis, we have
that $m_{k}(F\setminus u)$ is maximized when $F\setminus u=P_{n-1}$ and
$m_{k-1}(F\setminus uv)$ is maximized when $F\setminus uv=P_{n-2}$. This shows
that $m_{k}(F)$ is maximized if and only if $F=P_{n}$, completing the
induction. ∎

##  3 Maximum number of strong almost-perfect matchings

Recall that a strong almost-perfect matching (SAPM) is a matching which avoids
one leaf when $n$ is odd and two leaves when $n$ is even. In this section, we
characterize the trees that maximize the number of SAPMs with three theorems
which, combined, give a more complete version of Theorem 3.

We first define the relevant families of trees. Often a spider can refer to
any subdivision of a star, i.e. any tree which has at most one vertex of
degree at least $3$. We will refer to a spider $\operatorname{Sp}_{n}$ as the
unique spider of order $n$ whose legs all have length $2$, except possibly one
leg of length $1$ when $n$ is even.

######  Definition 10.

An odd spider is a $1$-subdivision of a star. An even spider is an odd spider
with an additional pendant edge added to the unique vertex of degree $\geq 3$.
We use the notation $\operatorname{Sp}_{n}$ for both. See Figure 1.

(a) An odd spider

(b) An even spider

Figure 1: Two spiders

######  Definition 11.

A double broom $\operatorname{DB}_{a,b}$ is a tree of diameter $3$ whose non-
leaves have degree $a+1$ and $b+1$ respectively. A balanced double broom on
$n$ vertices is a tree of diameter $3$ whose non-leaves have degree
$\lfloor\frac{n}{2}\rfloor$ on one side and $\lceil\frac{n}{2}\rceil$ on the
other side. See Figure 2.

$a$$b$ (a) A (balanced) double broom $\operatorname{DB}_{4,5}$

(b) A wide spider

Figure 2: A double broom and wide spider

######  Theorem 12.

Let $n$ be odd. If $n\geq 5$, a tree $T$ of order $n$ has at most
$\frac{n-1}{2}$ strong almost-perfect matchings.

For $n\geq 7$, equality holds if and only if $T$ is an odd spider.

For $n=5$, equality holds for both $\operatorname{DB}_{1,2}$ and $P_{5}.$

###### Proof.

If $T$ is a tree that contains two leaves with a common neighbor, then $T$ has
at most two SAPMs, since every matching must avoid at least one of these two
leaves. Otherwise, $T$ has at least as many internal vertices as leaves and
thus at most $\frac{n-1}{2}$ leaves. It follows that $T$ has at most
$\frac{n-1}{2}$ SAPMs. The $n$-vertex spider achieves this upper bound.

For $n=5$, we have $\frac{n-1}{2}=2$, and one can check by hand that the
extremal graphs are the path $P_{5}$ (which is a spider) and the double broom
$\operatorname{DB}_{1,2}$. For $n\geq 7$, let $T$ be a tree of order $n$ with
$\frac{n-1}{2}$ SAPMs. Then $T$ must have $\frac{n-1}{2}$ leaves
$\\{u_{i}:1\leq i\leq\frac{n-1}{2}\\}$. For each $i$, let $v_{i}$ be the
unique neighbor of $u_{i}$. This gives us $n-1$ vertices, so $T$ contains one
additional vertex $x$. For each $i$, $T\setminus\\{u_{i}\\}$ has a perfect
matching, which must contain $u_{j}v_{j}$ for all $j\neq i$. Thus, $x\sim
v_{i}$ for all $i$, and so $T$ is indeed a spider. ∎

When $n$ is even, an almost-perfect matching $M$ of $T$ contains all but two
vertices, so counting the number of almost-perfect matchings of $T$ is
equivalent to counting the number of avoided pairs $P\subset V(T)$ for which
$T\setminus P$ has a perfect matching. This is the strategy we employ to prove
the next theorem, in which we have the additional assumption that $T$ contains
a perfect matching.

######  Definition 13.

A wide spider is constructed by subdividing every pendant edge of a double
broom. For $n=2k$, the balanced wide spider $W_{n}$ on $n$ vertices is the
tree one obtains from subdividing every pendant edge of a balanced double
broom on $k+1$ vertices. See Figure 2.

######  Theorem 14.

Let $n$ be even. If $T$ is a tree of order $n$ that contains a perfect
matching, then the number of strong almost-perfect matchings in $T$ is at most

$\max\left\\{1,\frac{n-2}{2},\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}\right\\}=\begin{cases}1&n=2,\\\
\frac{n-2}{2}&2<n\leq 10,\\\
\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}&n\geq
10.\end{cases}$

Equality holds if and only if either

  * •

$n\leq 10$, and $T$ is obtained by attaching a leaf to each vertex of a tree
of order $\frac{n}{2}$, or

  * •

$n\geq 10$, and $T$ is the balanced wide spider.

###### Proof.

If $n=2$, then there is precisely one SAPM, namely the empty matching, so
assume that $n>2$. Let $T$ be an arbitrary tree of order $n$ with a perfect
matching. Let $\\{u_{1},\dots,u_{k}\\}$ be the leaves of $T$. Observe that no
two leaves have the same neighbor; else, the perfect matching would match both
with their common neighbor. It follows that $k\leq\frac{n}{2}$. Let $v_{i}$ be
the unique neighbor of $u_{i}$, $1\leq i\leq k$.

Recall that a bipartite graph can have a perfect matching only if the parts of
the bipartition are the same size. Consider the (unique) bipartition
$V(T)=X\cup Y$. An SAPM of $T$ that avoids $u_{i}$ and $u_{j}$ is a perfect
matching of $T\setminus\\{u_{i},u_{j}\\}$. This can occur only if $u_{i}$ and
$u_{j}$ belong to different parts of the bipartition $X\cup Y$. Thus, there
are at most $\mathopen{}\left\lfloor\frac{k^{2}}{4}\right\rfloor\mathclose{}$
SAPMs of $T$.

If $k=\frac{n}{2}$, then $T[\\{v_{1},\dots,v_{k}\\}]$ must be a tree of order
$\frac{n}{2}$, and every SAPM in $T$ can only avoid $u_{i}$ and $u_{j}$ such
that $v_{i}\sim v_{j}$. This gives $\frac{n}{2}-1=\frac{n-2}{2}$ SAPMs in $T$,
one for each edge of $T[\\{v_{1},\dots,v_{k}\\}]$.

Otherwise, $k\leq\frac{n}{2}-1=\frac{n-2}{2}$, which means that there are at
most $\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}$
SAPMs. This is achieved by the wide spider $W_{n}$. Indeed, for every pair of
leaves on opposite sides, there is an APM that avoids those leaves, so the
number of SAPMs in $W_{n}$ is
$\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}$.

Thus, we have shown that the maximum is

$\max\left\\{1,\frac{n-2}{2},\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}\right\\},$

and it remains to discuss the cases of equality. Note first that
$\frac{n-2}{2}\geq\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}$
if and only if $n\leq 10$ (with equality for $n=10$), so the case that there
are $k=\frac{n}{2}$ leaves yields the maximum for $2<n\leq 10$, while the case
that there are $k=\frac{n}{2}-1$ leaves and
$\mathopen{}\left\lfloor\frac{k^{2}}{4}\right\rfloor\mathclose{}$ SAPMs yields
the maximum for $n\geq 10$.

It only remains to show that the wide spider $W_{n}$ is unique in the second
case. Suppose $T$ has $k=\frac{n-2}{2}$ leaves and
$\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}$ almost-
perfect matchings. Let $x$ and $y$ be the two vertices that are neither leaves
nor neighbors of leaves. Their degree is at least $2$. The perfect matching of
$T$ must contain the edge $u_{i}v_{i}$ for all $i$, so $x\sim y$. Suppose
without loss of generality that $x\in X,y\in Y$. Then there is some $v_{i}\in
X,v_{j}\in Y$ such that $x\sim v_{j}$ and $y\sim v_{i}$.

Let $v_{\ell}\in X$ for $\ell\neq i$. Suppose for the sake of contradiction
that $v_{\ell}\not\sim y$. For each $m$ such that $v_{m}\in Y$, in order to
have a perfect matching of $T\setminus\\{u_{\ell},u_{m}\\}$, we must have
$v_{\ell}\sim v_{m}$. This implies $v_{m}\not\sim x$ for all $m\neq j$; else,
$\\{x,v_{j},v_{\ell},v_{m}\\}$ would form a cycle. Then there cannot be an
almost-perfect matching that avoids $u_{i}$ and $u_{m}$ for $m\neq j$, since
there is no disjoint set of edges to cover $v_{m},v_{\ell}$, and $u_{\ell}$,
which is a contradiction. This tells us that $v_{\ell}\sim y$ for all $\ell$
such that $v_{\ell}\in X$, and a similar argument shows that $v_{m}\sim x$ for
all $m$ such that $v_{m}\in Y$, and so $T$ is isomorphic to the balanced wide
spider. ∎

When we remove the requirement that $T$ contains a perfect matching, we can
still characterize the extremal examples as follows:

######  Definition 15.

An even special spider $\operatorname{SS}_{n}$ on $n$ vertices for $n$ even is
an odd spider $\operatorname{Sp}_{n-1}$ with a sibling added for one of the
leaves. See Figure 3.

A spider trio $\operatorname{ST}_{a,b,c}$ is a tree constructed from three
spiders $\operatorname{Sp}_{a}$, $\operatorname{Sp}_{b}$,
$\operatorname{Sp}_{c}$ whose center vertices are attached to a single new
vertex. See Figure 3.

(a) An even special spider $\operatorname{SS}_{n}$

$a$$b$$c$ (b) A spider-trio $\operatorname{ST}_{a,b,c}$

Figure 3: Other variants of spiders

######  Theorem 16.

Let $f(n)$ be the maximum number of SAPM’s in a tree $T$ of order $n$. Then,
for $n$ even,

$f(n)=\begin{cases}\mathopen{}\left\lfloor\frac{3n}{4}\right\rfloor\mathclose{}&\text{
if }2\leq n\leq 6,\\\ n-3&\text{ if }8\leq n\leq 14,\\\
\mathopen{}\left\lfloor\frac{n^{2}}{16}\right\rfloor\mathclose{}-1&\text{ if
}16\leq n\leq 28,\\\
\mathopen{}\left\lfloor\frac{(n-4)^{2}}{12}\right\rfloor\mathclose{}&\text{ if
}n\geq 28.\\\ \end{cases}$

Equality holds if and only if $T$ is one of the following trees:

$\begin{cases}P_{2},S_{4},\&\operatorname{DB}_{2,2}&\text{ for }2\leq n\leq
6,\\\ \operatorname{SS}_{n}&\text{ if }8\leq n\leq 12,\\\
\operatorname{SS}_{14}\&\operatorname{ST}_{3,2,0}&\text{ if }n=14,\\\
\operatorname{ST}_{\mathopen{}\left\lceil\frac{n-4}{4}\right\rceil\mathclose{},\mathopen{}\left\lfloor\frac{n-4}{4}\right\rfloor\mathclose{},0}&\text{
if }16\leq n\leq 26,\\\
\operatorname{ST}_{6,6,0}\&\operatorname{ST}_{4,4,4}&\text{ if }n=28,\\\
\operatorname{ST}_{\mathopen{}\left\lfloor\frac{n}{6}\right\rfloor\mathclose{},\mathopen{}\left\lfloor\frac{n-2}{6}\right\rfloor\mathclose{},\mathopen{}\left\lfloor\frac{n-4}{6}\right\rfloor\mathclose{}}&\text{
if }n\geq 28,\\\ \end{cases}$

###### Proof.

For $n\leq 16$, the values of $f(n)$ have been checked with a computer, so we
may assume $n\geq 18$. Let $T$ be a tree on $n$ vertices. If two leaves of $T$
share a common neighbor, then by Lemma 8, $T$ has at most $n$ SAPMs. Since
$f(n)>n$ (as evidenced by the trees given in the claim), $T$ cannot be
extremal in this case.

Thus, we may also assume that every leaf has a unique neighbor and so the
number of leaves is at most $\frac{n}{2}$. If $T$ has exactly $\frac{n}{2}$
leaves, then $T$ must also contain a perfect matching. By Theorem 14, $T$ has
at most $\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}$
SAPMs, which is smaller than both
$\mathopen{}\left\lfloor\frac{n^{2}}{16}\right\rfloor\mathclose{}-1$ and
$\mathopen{}\left\lfloor\frac{(n-4)^{2}}{12}\right\rfloor\mathclose{}$ when
$n\geq 18$.

Now suppose the number of leaves in $T$ is at most $\frac{n}{2}-1.$ Let
$V(T)=X\cup Y$ be the bipartition of $T$, and without loss of generality,
suppose $\lvert X\rvert\geq\lvert Y\rvert$. Recall that $T$ containing an
almost-perfect matching implies that either $\lvert X\rvert=\lvert Y\rvert$ or
$\lvert X\rvert=\lvert Y\rvert+2$. If $\lvert X\rvert=\lvert Y\rvert,$ then
every avoided pair of leaves must have one element in $X$ and one element in
$Y$. There are at most
$\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}$ such
pairs, which again is less than the stated upper bounds.

So now we assume that $\lvert X\rvert=\lvert Y\rvert+2=\frac{n}{2}+1.$

Case 1: $Y$ contains no leaves. Then the degree of every vertex in $Y$ is at
least $2$. As $\lvert Y\rvert=\frac{n-2}{2}$, and $\sum_{v\in Y}\deg(v)=n-1$,
this implies that all but one vertex in $Y$ has degree 2. Let $z$ be the
unique vertex in $Y$ which has degree 3.

In that case $T\setminus z$ has three components—call them $A,B,C$. Each
component is itself a tree whose vertices in $Y$ have degree 2. Thus each of
them has one more vertex in $X$ than in $Y$. In particular, each component has
an odd number of vertices in total.

Observe that if a component, say $C$, of $T\setminus z$ does not contain a
member of the avoided pair, then since $\lvert C\rvert$ is odd, the SAPM must
match $z$ with its neighbor in $C$. Thus, an avoided pair of leaves cannot be
contained in a single component.

Let $a,b,c$ be the number of leaves in $A,B$, and $C$ respectively, with
$a\geq b\geq c$. Then the number of SAPMs is bounded above by $ab+bc+ac.$ If
$B$ and $C$ are singletons, this gives an upper bound of $1+2a<n$. If only $C$
is a singleton, then we have
$ab+a+b=(a+1)(b+1)-1\leq\mathopen{}\left\lfloor\frac{n^{2}}{16}\right\rfloor\mathclose{}-1.$
Furthermore, we can see that equality is attained only for the tree
$\operatorname{ST}_{a,b,0}$ when $a=b=\frac{n}{4}$. Indeed, each SAPM of $T$
is a union of SAPMs of $A$ and $B$, and the edge from $z$ to $C$. By Theorem
12, $A$ and $B$ have the maximum number of SAPMs if and only if they are both
spiders.

Else, each neighbor of $z$ is a non-leaf vertex in $X$, and as such
$a+b+c\leq\frac{n-4}{2}.$ By the AM-GM inequality, we know that
$ab+bc+ac\leq\frac{(a+b+c)^{2}}{3}$ and since the number of SAPMs is an
integer, we conclude that
$\mathopen{}\left\lfloor\frac{(n-4)^{2}}{12}\right\rfloor\mathclose{}$ is an
upper bound. By a similar argument to the previous case, the extremal tree is
precisely the balanced spider-trio $\operatorname{ST}_{a,b,c}$ where $a\geq
b\geq c\geq a-1$. This has exactly
$\mathopen{}\left\lfloor\frac{(n-4)^{2}}{12}\right\rfloor\mathclose{}$ SAPMs.
It is now sufficient to note that
$\mathopen{}\left\lfloor\frac{n^{2}}{16}\right\rfloor\mathclose{}-1\leq\mathopen{}\left\lfloor\frac{(n-4)^{2}}{12}\right\rfloor\mathclose{}$
if and only if $n\geq 28.$

Case 2: There is a leaf $y\in Y$. Let $x$ be the unique neighbor of $Y$. Since
$\lvert X\rvert=\lvert Y\rvert+2$, every avoided pair must be contained in $X$
and so every almost-perfect matching must contain $xy$.

If $\deg(x)=2$, the number of SAPMs of $T$ equals the number of SAPMs of
$T\setminus\\{x,y\\}$, which is at most $f(n-2)$. Since $f(n-2)<f(n)$ for
every (even) positive integer $n$, the result follows from induction.

If $\deg(x)>2$ and $T\setminus\\{x,y\\}$ is a forest, the result also follows
similarly by induction since $T\setminus\\{x,y\\}$ is a subgraph of a tree. If
the components of $T\setminus\\{x,y\\}$ are all even, with orders
$n_{1},n_{2},\ldots n_{k}$, then there are at most
$f(n_{1})+f(n_{2})+\ldots+f(n_{k})<f(n)$ SAPM’s. If two components are odd, we
have at most
$\mathopen{}\left\lfloor\frac{(n-2)^{2}}{16}\right\rfloor\mathclose{}$ pairs
of leaves, one in each odd component. ∎

##  4 Minimum number of maximal matchings

In this section, we characterize trees with the minimum number of maximal
matchings. This complements the result of Górska and Skupień [4] on the
maximum number of maximal matchings.

######  Definition 17.

An odd special spider $\operatorname{SS}_{n}$ on $n$ vertices for $n$ odd is
an even spider $\operatorname{Sp}_{n-1}$ with a pendant edge added to the
center vertex (for $n\geq 7$, this is the unique vertex of degree $\geq 3$).
See Figure 4.

Figure 4: An odd special spider $\operatorname{SS}_{n}$

######  Theorem 4.

A tree $T$ of order $n$ has at least $\lceil\frac{n}{2}\rceil$ maximal
matchings. Equality holds if and only if $T$ is a spider
$\operatorname{Sp}_{n}$, or an odd special spider $\operatorname{SS}_{n}$.

###### Proof.

We proceed by induction on $n$. A small computer verification confirms the
claim for $n\leq 7$ (the paths $P_{n}$ are also spiders
$\operatorname{Sp}_{n}$ when $n\leq 5$). Now let $n\geq 8$. We consider two
cases. Either there are two leaves $u_{1},u_{2}$ with a common neighbor $v$,
or there is a leaf $u$ whose unique neighbor $v$ has degree $2$, i.e., has
only $2$ neighbors $\ell_{1}$ and $u.$

In the first case, let $T^{\prime}=T\setminus\\{u_{1},u_{2}\\}$. Observe that
every maximal matching $M$ of $T^{\prime}$ can be extended to a maximal
matching of $T$. If $M$ covers $v$, then $M$ is also a maximal matching of
$T$. If $M$ does not contain $v$, then we can extend $M$ with $u_{1}v$ or with
$u_{2}v$.

In the second case, let $T^{\prime}=T\setminus\\{u,v\\}$ and let $x$ be the
other neighbor of $v$. As before, every maximal matching $M$ of $T^{\prime}$
can be extended to a maximal matching of $T$. If $M$ covers $x$, the unique
extension is given by $M\cup\\{uv\\}$. If $M$ does not cover $x$, we can
extend using either $uv$ or $vx$.

Since we can always find a maximal matching of $T$ that uses $u_{2}v$ ($uv$,
respectively; in general any particular edge), we note that $T$ has strictly
more maximal matchings than $T^{\prime}$ and we conclude by induction.

For equality to be attained by $T$, equality need to be attained by
$T^{\prime}$ and thus $T^{\prime}$ is a spider or a special spider (if $n$ is
odd). Note that $T^{\prime}$ has at least two legs of length $2$ and thus $T$
has at least one leg $L$ of length $2$. By applying the inductive hypothesis
to $T\setminus L$, we know that $T\setminus L$ has to be either
$\operatorname{Sp}_{n-2}$, or $\operatorname{SS}_{n-2}$ if $n$ is odd. We can
then conclude that $T$ itself is $\operatorname{Sp}_{n}$ or
$\operatorname{SS}_{n}$, and these indeed attain equality. ∎

Initially, this question about determining the minimum number of maximal
matching was motivated by the following observation about maximal matchings,
which we will utilize in applications to the weighted Hosoya index.

######  Lemma 18.

If $n\geq 2$, then the sum of degrees in a maximal matching $M$ in a tree $T$
of order $n$ is at least $n$. Equality occurs only if $T$ is a star, or $T$
has diameter $3$ and $M$ is the central edge.

Note that the statement is trivially false for a $1$-vertex tree, so $n\geq 2$
is required.

###### Proof.

Let $M$ be a maximal matching. If $v\in V$ is not covered by $M$, then there
must exist some $u\in N(v)$ that is covered by $M$; else, $M\cup\\{uv\\}$ is a
larger matching, contradicting the maximality of $M$. This implies that
$\bigcup\\{N(u):u\text{ is covered by }M\\}=V$, from which the statement
follows.

Equality can occur only if every vertex has precisely one neighbor covered by
the matching. By the argument above, for every $v$ not covered by $M$, we must
have all of $N(v)$ covered by $M$. This implies that all non-leaf vertices of
$T$ are covered by $M$. If the diameter of $T$ is at least $4$, then there
exist internal vertices of a diameter path which have more than one neighbor
covered by $M$, and so equality does not occur. If $T$ has diameter $3$, there
are only two types of maximal matchings and we conclude easily. ∎

As a corollary of Theorem 4 and Lemma 18, we have the following result on the
weighted Hosoya index. This is a special case of a more general theorem that
we prove in the next section. Recall that $S_{n}$ denotes the $n$-vertex star.

######  Corollary 19.

Let $\phi(i,j)=c^{i+j}$ where $c\geq 2$. Then for every $n$-vertex tree $T$,
we have $Z_{\phi}(S_{n})\leq Z_{\phi}(T)$.

###### Proof.

First note that $S_{n}$ has $n-1$ nonempty matchings, each with weight
$c^{n}$, so $Z_{\phi}(S_{n})=(n-1)c^{n}+1$. For a tree $T$ that is not a star,
by Theorem 4, $T$ has at least $\lceil\frac{n}{2}\rceil$ maximal matchings,
and by Lemma 18, each has degree sum strictly greater than $n$, with possibly
one exception which has degree sum exactly equal to $n$. Thus we have
$Z_{\phi}(T)>\left(\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}-1\right)c^{n+1}+c^{n}+1\geq(n-1)c^{n}+1=Z_{\phi}(S_{n})$.
The first inequality is strict since there are pendant edges which are not
maximal matchings and contribute in the sum as well. The second inequality
holds by our assumption $c\geq 2$. ∎

##  5 Applications to the weighted Hosoya index

Recall that the weighted Hosoya index is defined as

$Z(T,\omega)=\sum_{M\in\mathcal{M}}\prod_{e\in M}\omega(e)$

In this section, we characterize the extremal examples for some natural
choices of weights that are vertex-degree-based, meaning $\omega(e)=\phi(i,j)$
where $i$ and $j$ are the degrees of the endpoints of $e$. We then write
$Z(T,\omega)$ as $Z_{\phi}(T)$.

We consider the following weight functions for $c>0$:

$\displaystyle\phi_{1}(i,j)$ $\displaystyle=c^{i+j}$
$\displaystyle\phi_{2}(i,j)$ $\displaystyle=c^{ij}$
$\displaystyle\phi_{3}(i,j)$ $\displaystyle=(i+j)^{c}$
$\displaystyle\phi_{4}(i,j)$ $\displaystyle=(ij)^{c}$

Note that these examples are all symmetric in $i$ and $j$. It was shown in [1]
that for $c<0$, the star minimizes the weighted Hosoya index for $\phi_{3}$
and $\phi_{4}$ (also referred to as the general Randić index and general sum-
connectivity index, respectively). This can also be derived from the following
proof that the star minimizes the weighted Hosoya index for $c>0$.

######  Theorem 20.

Let $c>0$. Then for every $n$-vertex tree $T$, we have $Z_{\phi_{\ell}}(T)\geq
Z_{\phi_{\ell}}(S_{n})$ for all $\ell\in[4]=\\{1,2,3,4\\}$. Equality holds in
each case if and only if $T=S_{n}$.

###### Proof.

Let $Z_{\phi}(T,v,k)$ be the weighted Hosoya index of $T$ where the weight of
$v$ is increased by $k$. That is, if $uv=e\in E(T)$ for some $u$, then
$\phi(e)=\phi(\deg(u),\deg(v)+k)$. We will use induction to prove a stronger
statement:

######  Claim 21.

Let $T$ be a tree on $n$ vertices, and let $v\in V(T)$ be a non-leaf vertex
that has at least one leaf neighbor. For any nonnegative integer $k$ and
$\ell\in[4]$, $Z_{\phi_{\ell}}(T,v,k)\geq Z_{\phi_{\ell}}(S_{n},x,k)$ where
$x$ is the center vertex of the star.

Observe that taking $k=0$ gives the theorem statement.

We proceed by induction on $n$. We can check the first non-trivial base case
($n=4$) directly to see that the claim holds true for all $k\geq 0$ and all
$c>0$.

Now suppose that for every $n^{\prime}<n$, the claim holds for all $k\geq 0$.

Let $T$ be an $n$-vertex tree different from $S_{n}$, and let $k$ be a
nonnegative integer. Let $v\in T$ be a non-leaf vertex. Let
$u_{1},\dots,u_{s}$ be the leaf neighbors of $v$ and let $x_{1},\dots,x_{t}$
be the non-leaf neighbors. Let $T_{i}$ be the component of $x_{i}$ in
$T\setminus\\{v,u_{1},\dots,u_{s}\\}$. Then

$Z_{\phi}(T,v,k)=Z_{\phi}(T\setminus\\{\ell_{1},\dots,\ell_{s}\\},v,s+k)+s\phi(1,deg(v)+k)\prod_{i=1}^{t}Z_{\phi}(T_{i},x_{i},1)$

Given a star graph $S_{n}$, let $z_{n}$ denote the center vertex.

First consider $\phi_{1}(i,j)=c^{i+j}$. We can calculate that
$Z_{\phi_{1}}(S_{n},z_{n},k)=(n-1)c^{n+k}+1$. By the inductive hypothesis,

$\displaystyle Z_{\phi_{1}}(T,v,k)$ $\displaystyle\geq
Z_{\phi_{1}}(S_{n-s},z_{n-s},s+k)+s\phi_{1}(1,s+t+k)\prod_{i=1}^{t}Z_{\phi_{1}}(S_{|T_{i}|},z_{|T_{i}|},1)$
$\displaystyle\geq(n-s-1)c^{(n-s)+(s+k)}+1+sc^{(s+t)+k+1}\prod_{i=1}^{t}((|T_{i}|-1)c^{|T_{i}|+1}+1)$

Observe that $\sum_{i=1}^{t}|T_{i}|=n-s-1$, so we have

$\displaystyle Z_{\phi_{1}}(T,v,k)$
$\displaystyle\geq(n-s-1)c^{n+k}+1+sc^{s+t+k+1}\left(c^{(n-s-1)+t}\prod_{i=1}^{t}(|T_{i}|-1)+1\right)$
$\displaystyle=(n-s-1)c^{n+k}+1+sc^{n+2t+k}\prod_{i=1}^{t}(|T_{i}|-1)+sc^{s+t+k+1}$

We want the last expression to be at least $(n-1)c^{n+k}+1$. Recall that
$s\geq 1$ by assumption. Dividing both sides of the desired inequality by
$sc^{n+k}$ and rearranging, it suffices to show

$c^{2t}\prod_{i=1}^{t}(|T_{i}|-1)+c^{s+t+1-n}\geq 1$

If $T$ is not isomorphic to $S_{n}$, then $t\geq 1$ and $|T_{i}|\geq 2$ for
all $i$, so when $c\geq 1$, the first term is at least 1 and the inequality
holds. The second term is also positive, so the inequality must be strict in
this case.

When $c<1$, we use that $n=(s+1)+\sum_{i=1}^{t}|T_{i}|\geq s+1+2t$, so the
second term is at least $1$, and as before, the inequality holds and is strict
for $T\neq S_{n}$.

(Note that we may separately address the case $c<1$ for $\phi_{1}$. Since $T$
is a tree, $\deg(u)+\deg(v)\leq n$ for every edge $uv$ in $T$. Thus,
$Z_{\phi_{1}}(T)\geq(n-1)c^{n}+1$ where equality holds if and only if $T$ is
the star. However, this argument does not apply to the case of, for example,
$\phi_{2}(i,j)=c^{ij}$.)

The calculations are almost identical for $\phi_{2},\phi_{3}$, and $\phi_{4}$,
so we omit most of the details here. For $\phi_{2}$, we arrive at

$Z_{\phi_{2}}(T,v,k)\geq(n-s-1)c^{n+k-1}+1+sc^{n+t+k-1}\prod(|T_{i}|-1)+sc^{s+t+k}$

and similarly show that this is at least $(n-1)c^{n+k-1}+1$ with equality if
and only if $T=S_{n}$.

For $\phi_{3}$, we have

$Z_{\phi_{3}}(T,v,k)\geq(n-s-1)(n+k)^{c}+1+s(s+t+k+1)^{c}\prod(|T_{i}|+1)^{c}$

Since $n+k<n+k+t=(s+t+k)+\sum|T_{i}|+1$ and each of the terms $(s+t+k)$ and
$\sum|T_{i}|$ is at least $2$, we know that $n+k\leq(s+t+k+1)\prod(|T_{i}|+1)$
and so the result follows.

Lastly, for $\phi_{4}$, we have

$Z_{\phi_{4}}(T,v,k)\geq(n-s-1)(n+k-1)^{c}+1+s(s+t+k)^{c}\prod(|T_{i}|)^{c}$

and similarly the result follows from $n+k-1\leq(s+t+k)\prod|T_{i}|$. ∎

From this and previous work on the Hosoya index, one might be tempted to
conjecture that the path and the star are always extremal, even if not
uniquely so. It turns out this is not the case.

######  Theorem 22.

For $c$ sufficiently large in terms of $n$, the tree that (uniquely) maximizes
$Z_{\phi_{\ell}}(T)$ among all trees of order $n$ is

  * •

$\ell=1$: $W_{n}$ if $n\geq 12$ is even and $\operatorname{Sp}_{n}$ if $n\geq
7$ is odd,

  * •

$\ell=2$:
$\operatorname{DB}_{\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{}-1,\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}-1}$
if $n\geq 6,$

  * •

$\ell\in\\{3,4\\}$: $P_{n}$

###### Proof for $\phi_{1}$.

Recall that $\phi_{1}(i,j)=c^{i+j}$. Suppose first that $n$ is even. For a
perfect matching $M$, we must have

$\sum_{e=uv\in M}\left(\deg(u)+\deg(v)\right)=2(n-1)$

Thus, for $c\geq 1$, the leading term of $Z_{\phi_{1}}(T)$ is at most
$c^{2n-2}$ (since every tree has at most one perfect matching). The second
leading term corresponds to the weight of strong almost-perfect matchings in
$T$, which must each have weight $c^{2n-4}$. Because we are taking $c$
sufficiently large, it is enough to recall from Theorem 14 that the balanced
wide spider uniquely maximizes the number of SAPMs for $n\geq 12$.

If $n$ is odd, the leading term of $Z_{\phi_{1}}(T)$ is given by SAPMs which
each have weight $c^{2n-3}$. From Theorem 12, we know that the odd spider has
the maximum number of SAPMs when $n\geq 7$. ∎

###### Proof for $\phi_{2}$.

To prove the result for $\phi_{2}(i,j)=c^{ij}$ we use the following claim.

######  Claim 23.

Let $T$ be a tree of order $n\geq 6$ and $M$ a matching of $T$. Then
$\sum_{uv\in
M}\deg(u)\cdot\deg(v)\leq\mathopen{}\left\lfloor\frac{n^{2}}{4}\right\rfloor\mathclose{}$,
with equality if and only if $T$ is the balanced double-broom with diameter
$3$ and $M$ consists of the central edge.

###### Proof of Claim.

Let $M=\\{e_{1},\dots,e_{k}\\}$ and for every $i$, let $d_{i}$ be the sum of
the degrees of the endpoints of $e_{i}$. Assume the edges are ordered such
that $d_{1}\leq d_{2}\leq\cdots\leq d_{k}$. Since $n>2$, we know $d_{i}\geq 3$
for every $i$. There are $n-2k$ vertices not covered by $M$, so by the
handshaking lemma, we know that $\sum_{i=1}^{k}d_{i}\leq
2(n-1)-(n-2k)=n+2k-2.$ If $k=1$, then $M$ consists of a single edge $uv$ and
by the AM-GM inequality,

$\deg(u)\deg(v)\leq\mathopen{}\left\lfloor\frac{d_{1}^{2}}{4}\right\rfloor\mathclose{}\leq\mathopen{}\left\lfloor\frac{n^{2}}{4}\right\rfloor\mathclose{}$

When $k\geq 2$, it suffices to prove that

$\sum_{i}\mathopen{}\left\lfloor\frac{d_{i}^{2}}{4}\right\rfloor\mathclose{}\leq\mathopen{}\left\lfloor\frac{n^{2}}{4}\right\rfloor\mathclose{}.$

In this case, we apply Lemma 7. Consider the sequences
$A=(3,3,\dots,3,\sum_{i=1}^{k}d_{i}-3(k-1))$ with the first $k-1$ terms equal
to 3, and $B=(d_{1},\dots,d_{k})$. Both sequences sum to $\sum_{i=1}^{k}d_{i}$
and since $d_{i}\geq 3$ for all $i$, we have that for any $\ell<k$, the sum of
the first $\ell$ terms of $A$ is at most the sum of the first $\ell$ terms of
$B$. This means that $A$ majorizes $B$, so we may apply Karamata’s inequality
with the convex function $f(x)=x^{2}$ to get that
$\sum_{i=1}^{k}d_{i}^{2}\leq(k-1)3^{2}+((n+2k-2)-3(k-1))^{2}=n^{2}-(k-1)(2n-k-8)<n^{2}-1,$
where we use that $n\geq\max\\{6,2k\\}$ and conclude.

Since the last inequality is strict, equality cannot be achieved by any
matching of size at least two. In the case $k=1$, the extremal tree must
contain an edge whose endpoints each have degree $\frac{n}{2}$; the balanced
double-broom is the unique example. ∎

Now let $T$ be a tree of order $n$ such that
$T\not=\operatorname{DB}_{\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{}-1,\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}-1}$.
We know that $|\mathcal{M}(T)|\leq F_{n}$, the $n$th Fibonacci number. Thus,

$Z_{\phi_{2}}(T)\leq
F_{n}c^{\mathopen{}\left\lfloor\frac{n^{2}}{4}\right\rfloor\mathclose{}-1}<c^{\mathopen{}\left\lfloor\frac{n^{2}}{4}\right\rfloor\mathclose{}}<Z_{\phi_{2}}\left(\operatorname{DB}_{\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{}-1,\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}-1}\right).$

∎

###### Proof for $\phi_{3}$.

For $\phi_{3}(i,j)=(i+j)^{c}$, the leading term of $Z_{\phi_{3}}$ does not
correspond with a unique graph. We first prove a general claim about
maximizing the product of a set of integers, which follows from Karamata’s
inequality.

######  Claim 24.

Assume integers $a_{1},a_{2},\ldots,a_{k}$ sum to $qk+r$, where $0\leq r<q$.
Then $\prod_{i=1}^{k}a_{i}\leq(q+1)^{r}q^{k-r}$ and equality occurs only if
$r$ of the $a_{i}$ equal $q+1$ and $k-r$ of them equal $q.$

###### Proof.

Let the $a_{i}$ be ordered such that $a_{1}\geq a_{2}\geq\ldots\geq a_{k}.$
Then $\sum_{i=1}^{\ell}a_{i}\geq\ell(q+1)$ for every $\ell\leq r.$ If not,
$a_{i}\leq q$ for every $i\geq\ell$ and thus
$\sum_{i=1}^{k}a_{i}\leq\ell(q+1)-1+(k-\ell)q<kq+\ell\leq kq+r,$ a
contradiction. Similarly, the sum of the $\ell\leq k-r$ smallest values among
the $a_{i}$ is bounded by $\ell q.$ This implies that the sequence
$(a_{1},a_{2}\ldots,a_{k})$ majorizes the sequence

$\left(\underbrace{q+1,q+1,\ldots,q+1}_{r},\underbrace{q,q,\ldots,q}_{k-r}\right).$

By Lemma 7 applied to the concave function $\log(x),$ we conclude that
$\sum_{i}\log(a_{i})\leq r\log(q+1)+(k-r)\log(q).$ ∎

######  Claim 25.

Let $T$ be a tree of order $n\geq 4$ and $M$ a matching in $T$. Then

$\prod_{uv\in M}\left(\deg(u)+\deg(v)\right)\leq\begin{cases}3^{2}\cdot
4^{(n-4)/2}&\text{ if n is even,}\\\ 3\cdot 4^{(n-3)/2}&\text{ if n is
odd.}\\\ \end{cases}$

Equality is possible only if $M$ is a perfect matching (for $n$ even) or
strong almost-perfect matching (for $n$ odd). Moreover, for all other
matchings the upper bound can be reduced by a factor of $2$.

###### Proof of Claim.

Let $V=\\{v_{1},\ldots,v_{n}\\}$ be an arbitrary permutation of the vertices
and $d_{i}=\deg(v_{2i-1})+\deg(v_{2i})$ (observe that $v_{2i-1}v_{2i}$ is not
necessarily an edge of $T$). If $n=2k$ is even, then
$\sum_{i=1}^{k}d_{i}=2n-2=4k-2$ by the handshaking lemma and by Claim 24,
$\prod_{i=1}^{k}d_{i}\leq 3^{2}\cdot 4^{k-2}.$ Equality happens only when all
$d_{i}$ are $3$ or $4$. If $M$ is not a perfect matching and covers vertices
$\\{v_{1},\dots,v_{2m}\\}$ (without loss of generality), then $2m<2k$ so we
may divide both sides by $d_{k}\geq 2$ to get the final part of the claim.

If $n=2k+1$ is odd, then $\sum_{i=1}^{k}d_{i}\leq 2(n-1)-1=4k-1$ and
$\prod_{i=1}^{k}d_{i}\leq 3\cdot 4^{k-1}$ by Claim 24. Similar arguments hold
for equality and when $M$ is not an SAPM as in the even case. ∎

We say $uv$ is an $(a,b)$-edge if $\deg(u)=a,\deg(v)=b$. To determine which
tree achieves equality in the previous claim, a trivial but crucial
observation is that $\deg(u)+\deg(v)=4$ if and only if $uv$ is a $(2,2)$\- or
$(3,1)$-edge. The path $P_{n}$ is a tree that attains equality in Claim 25,
but not the unique one.

First, consider the case where $n=2k+1$ is odd. The leading terms for
$Z_{\phi_{3}}(P_{n})$ are $2\cdot(3\cdot 4^{k-1})^{c}+(k-1)\cdot(3^{2}\cdot
4^{k-2})^{c}.$

Let $T\not=P_{n}$ be a tree of order $n$. The (strong) almost-perfect
matching(s) for which equality is attained in Claim 25 consist of $(3,1)$\-
and $(2,2)$-edges with exactly one $(2,1)$-edge. Observe that the extremal
tree must then consist of a central path (the diameter) with pendant leaves
connected to the internal vertices. There are at most two choices for an SAPM
that attains equality in Claim 25. If there is only one $(2,1)$-edge in $T$
(an example is presented in Figure 5 on the left), then there are two leaves
with the same neighbor of degree $3$ and hence only $2$ APM’s in total (since
an APM must contain exactly one of the two neighboring leaves). That implies
whenever $c$ is sufficiently large that

$Z_{\phi_{3}}(T)<2\cdot(3\cdot 4^{k-1})^{c}+F_{n}\cdot(3\cdot
4^{k-1}/2)^{c}<Z_{\phi_{3}}(P_{n})$

If there are two $(2,1)$-edges in $T$, let $u$ and $v$ be the two leaves at
the end of the diameter. Observe that we cannot have perfect matchings of both
$T\setminus u$ and $T\setminus v$; this is because $T$ has a $(3,1)$-edge
(since $T\neq P_{n}$) which must be contained in both matchings. Deleting the
endpoints of the $(3,1)$-edge splits the tree into two components, both of
which have odd order in one of $T\setminus u$ or $T\setminus v$. So in this
case there is at most one matching for which equality in Claim 25 holds. Thus
the leading term in $Z_{\phi_{3}}(T)$ is smaller than $2\cdot(3\cdot
4^{k-1})^{c}$ and the result follows again.

Figure 5: Trees for which $Z_{\phi_{3}}(T)$ and $Z_{\phi_{3}}(P_{n})$ have the
same leading term

Next, we consider the case where $n$ is even. A tree $T$ that attains equality
in Claim 25 has maximum degree at most $3$, every vertex of degree $3$ has a
neighboring leaf, and $T$ has a perfect matching (see the right hand side of
Figure 5 for an example). As before, $T$ consists of a diameter with pendant
leaves. The second largest contribution to $Z_{\phi_{3}}(T)$ would be due to a
strong almost-perfect matching $M$, for which $\prod_{uv\in
M}\left(\deg(u)+\deg(v)\right)\leq 2^{n-2}$ by Claim 25, and equality occurs
only if the avoided pair are the endpoints of the diameter, and the degree $3$
vertices in $M$ are paired with leaves.

Let the diameter have vertices $v_{1},v_{2},\dots,v_{k}$ where
$\\{v_{1},v_{k}\\}$ is the avoided pair, and let $i$ be minimum such that
$\deg(v_{i})=3$. In order for $M$ to cover the vertices $v_{2},\dots,v_{i-1}$,
we must have $i$ even. But $T$ has a perfect matching, and in order for the
perfect matching to cover $v_{1},v_{2},\dots,v_{i-1}$, we must have $i$ odd -
a contradiction unless $T$ contains no vertices of degree 3, i.e. $T=P_{n}$. ∎

###### Proof for $\phi_{4}$.

Finally, to prove the result for $\phi_{4}(i,j)=(ij)^{c}$ we use the following
claim.

######  Claim 26.

Let $T$ be a tree on $n\geq 2$ vertices. Then the product of the degrees of
all vertices is at most $2^{n-2}$, with equality if and only if $T$ is a path
$P_{n}$.

###### Proof.

A tree has at least $2$ leaves, so by the handshaking lemma the other $n-2$
vertices have degree $2$ on average. The claim follows from the AM-GM
inequality and the fact that the path is the only tree with exactly two
leaves. ∎

As such, the leading term of $Z_{\phi_{4}}(P_{n})$ is
$\left(2^{n-2}\right)^{c}$, while for any other tree $T$ of order $n$, we have
$Z_{\phi_{4}}(T)\leq F_{n}\left(3\cdot 2^{n-4}\right)^{c},$ which is smaller
than $\left(2^{n-2}\right)^{c}$ once e.g. $c>2n.$ ∎

##  6 Further Directions

We conclude with some further open problems.

###  6.1 Maximum number of strong $k$-almost-perfect matchings for $k\geq 3$

We can generalize the notion of an almost-perfect matching to a $k$-almost-
perfect matching ($k$-APM), a matching which covers all but $k$ vertices.
Similarly, a strong $k$-almost-perfect matching ($k$-SAPM) covers all but $k$
leaves. Observe that $k\in\\{1,2\\}$ recovers our original notion of APM and
SAPM. For $k\geq 3$, we can consider the question of which trees have the
maximum number of $k$-SAPMs.

In Theorem 16, for $n$ sufficiently large, we showed that the spider-trio
maximizes the number of SAPMs. For $n$ sufficiently large, one could hope that
a generalisation of the spider-trio, presented in Figure 6 for $k=7$, is
extremal. This might be true for small $k$ but is false for $k\geq 13$. When
$k=13$ a tree consisting of spiders connected to a path has more $k$-SAPMs
than the $(k+1)$-spider. Asymptotically, however, the generalized
$(k+1)$-spider has the optimal order.

Figure 6: A construction $T$ with $k+1$ spiders.

######  Proposition 27.

The number of strong $k$-almost-perfect matchings in a tree of order $n$ is
$\Theta_{k}(n^{k}).$

###### Proof.

The number of $k$-SAPMs is bounded by $\binom{n}{k}=O_{k}(n^{k})$. For the
lower bound, let $T$ be the union of $k+1$ odd spiders all of order $2a+1$,
whose centers are connected with an additional vertex $v$ as in Figure 6. Then
$n=(k+1)(2a+1)+1$ and the number of $k$-SAPMs in $T$ is
$(k+1)a^{k}\sim\frac{n^{k}}{2^{k}(k+1)^{k-1}}=\Omega_{k}(n^{k}).$ ∎

We can also determine some structural properties that the extremal tree(s)
must have.

######  Proposition 28.

If $T$ contains two leaves that share a common neighbor, then the number of
strong $k$-almost-perfect matchings is at most $2\binom{n}{k-1}=O(n^{k-1}).$

###### Proof.

If two leaves, $\ell_{1}$ and $\ell_{2},$ have the same neighbor, then no
matching can contain both of them. Thus, in any $k$-APM at least one of the
two is in the avoided set of $k$ leaves. For both $\ell_{1}$ and $\ell_{2}$,
the number of $k$-APMs is bounded by the number of ways to choose the
remaining $k-1$ leaves to avoid. ∎

As a consequence, for $n$ sufficiently large, we can partition the vertices
into three sets: the set of leaves $L$, the set of (unique) neighbors of the
leaves $N:=N(L)$ and the set of vertices $X$ that are at distance at least two
from any leaf. Observe that $\lvert L\rvert=\lvert N\lvert$ and $\lvert
X\rvert+2\lvert L\rvert=n$.

######  Proposition 29.

The number of strong $k$-almost-perfect matchings that contain an edge in
$T[N]$ is $O_{k}(n^{k-1}).$

###### Proof.

A $k$-SAPM $M$ is uniquely determined by the avoided set of $k$ leaves. If
there is an edge in $T[N]\cap M$, then the endpoints have neighbors in $L$
which must also be in the avoided set, together with $k-2$ other leaves. There
are fewer than $n-1$ edges in $T[N]$ and $O(n^{k-2})$ choices for the other
$k-2$ leaves, which results in a total of $O(n^{k-1})$ $k$-SAPMs that contain
an edge in $T[N]$. ∎

Thus, there are few $k$-SAPMs that contain an edge between two vertices in
$N$. We suspect the extremal trees are spiders connected to a relatively small
$X$, but the structure of $X$ seems difficult to characterize. Surprisingly,
when $T[X]$ is a path, the optimal number of leaves in each spider is not
monotone as the following example illustrates.

######  Example 30.

When $T$ is the union of $8$ spiders whose centers are connected with a path,
such that $T$ is symmetric, the number of strong $4$-APM’s is maximized when
the ratios of their sizes (counted from outer to inner spiders) is
approximately $\frac{27}{16}\colon 1\colon\frac{9}{16}\colon\frac{3}{4}.$

$a$$b$$c$$d$$d$$c$$b$$a$ Figure 7: A construction where $T[X]=P_{8}$

To see this, let the number of leaves of the $8$ spiders be $a,b,c,d,d,c,b,a$
respectively, as presented in Figure 7. Then $2(a+b+c+d)=\frac{n-8}{2}.$ A
strong $4$-APM can only be obtained when taking four leaves from different
spiders in such a way that the centers of the other four form a matching in
the path. The total number of choices for these leaves is equal to
$(b^{2}+(2c+2d)b+d^{2})a^{2}+2c((c+2d)b+d^{2})a+c^{2}d^{2}.$ Using a small
computer verification111https://github.com/StijnCambie/MRC_trees_projects,
document OptimalDistributionBehaviour., we conclude that this homogenous
multivariate polynomial is maximized when $(a\colon b\colon c\colon
d)=\left(\frac{27}{16}\colon 1\colon\frac{9}{16}\colon\frac{3}{4}\right).$

The preceding discussion may provide some intuition to tackle the following
question:

######  Question 31.

For $k\geq 3$, characterize the trees which maximize the number of strong
$k$-almost-perfect matchings.

We can generalize the notion of $k$-SAPM even further to that of a connected
matching, which is a matching $M$ in a tree $T$ such that $T[V(M)]$ is a
connected graph. The notion of connected matching (among some other variants)
was defined in [3]. Observe that every $k$-SAPM is a connected matching.
Conversely, when $n$ is odd, a connected matching with $\frac{n-1}{2}$ edges
is an SAPM. One could ask similar questions about characterizing the extremal
trees for connected matchings. It may be interesting to consider these type of
questions for connected matchings in general graphs as well, or classes such
as $d$-regular graphs which are well-studied in matching theory.

###  6.2 Weighted Hosoya index

Regarding applications to the weighted Hosoya index, it would be interesting
to determine the extremal trees for various other choices of degree-based
weight function. In particular, can we characterize when the path and the star
are the maximizer and minimizer, respectively?

For example, consider the function

$\phi(i,j)=\varphi^{16\lfloor\frac{ij}{16}\rfloor}$

where $\varphi$ is the golden ratio. While this choice of weight function may
seem rather artificial, it is interesting to note that neither $P_{n}$ nor
$S_{n}$ are extremal; one can check that
$Z_{\phi}(P_{n})=F_{n}\sim\varphi^{n}$ and
$Z_{\phi}(S_{n})=(n-1)\varphi^{n-1}$. Here $F_{n}$ is the $n^{th}$ Fibonacci
number. In fact, a weight of at least approximately $\varphi^{8n/3}$ can be
achieved by the construction in Figure 8 below.

(a) A graph with large $Z_{\phi}(G)$

(b) A graph with small $Z_{\phi}(G)$

Figure 8: Two trees indicating that $P_{n}$ and $S_{n}$ are not extremal

On the other hand, a weight of at most $8^{n/7}<\varphi^{3n/4}$ is given by
the construction in Figure 8.

One might try to generalize the results of Section 5 to answer the following:

######  Question 32.

Can we fully characterize the class of functions $\phi$ for which
$Z_{\phi}(T)$ is minimized by the star, or maximized by the path?

## Acknowledgments

The authors would like to express their gratitude to the American Mathematical
Society for organizing the Mathematics Research Community workshops where this
work began, in the workshop “Trees in Many Contexts,” and to Wanda Payne for
contributing to the initial discussions. This event was supported by the
National Science Foundation under Grant Number DMS $1916439$.

The first author is supported by the Institute for Basic Science
(IBS-R029-C4). The fourth author is supported by the Knut and Alice Wallenberg
Foundation (KAW 2017.0112).

#### Open access statement.

For the purpose of open access, a CC BY public copyright license is applied to
any Author Accepted Manuscript (AAM) arising from this submission.

## References

  * [1] R. Cruz, I. Gutman, and J. Rada.  Hosoya index of VDB-weighted graphs.  Discrete Applied Mathematics, 317:18–25, 2022.
  * [2] D. Gale and L. Shapley.  College admissions and the stability of marriage.  Amer. Math. Monthly, 69(1):9–14, 1962.
  * [3] W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, and R. Laskar.  Generalized subgraph-restricted matchings in graphs.  Discrete Math., 293(1-3):129–138, 2005.
  * [4] J. Górska and Z. Skupień.  Trees with maximum number of maximal matchings.  Discrete Math., 307(11-12):1367–1377, 2007.
  * [5] I. Gutman.  Graphs with greatest number of matchings.  Publ. Inst. Math. (Beograd) (N.S.), 27(41):67–76, 1980.
  * [6] P. Hall.  On representatives of subsets.  J. London Math. Soc., 10:26–30, 1935.
  * [7] H. Hosoya.  Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons.  Bull. Chem. Soc. Jpn., 44(9):2332–2339, 1971.
  * [8] D. Y. Kang, J. Kim, Y. Kim, and H.-F. Law.  On the number of $r$-matchings in a tree.  Electron. J. Combin., 24(1):Paper No. 1.24, 16, 2017.
  * [9] J. Karamata.  Sur une inégalité rélative aux fonctions convexes.  Publ. Math. Univ. Belgrade, 1:145–148, 1932.
  * [10] Y. Liu and J. Hao.  The enumeration of near-perfect matchings of factor-critical graphs.  Discrete mathematics, 243(1-3):259–266, 2002.
  * [11] L. Lovász and M. D. Plummer.  Matching theory, volume 121 of Annals of Discrete Mathematics, 29.  North-Holland Publishing Co., Amsterdam, 1986.
  * [12] R. Simion.  Trees with 1-factors and oriented trees.  Discrete Mathematics, 88(1):93–104, 1991.
  * [13] W. T. Tutte.  The factorization of linear graphs.  J. London Math. Soc., 22:107–111, 1947.
  * [14] S. Wagner and I. Gutman.  Maxima and minima of the Hosoya index and the Merrifield-Simmons index: a survey of results and techniques.  Acta Appl. Math., 112(3):323–346, 2010.
  * [15] S. Wagner and H. Wang.  Introduction to chemical graph theory.  Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2019.
  * [16] H. S. Wilf.  The number of maximal independent sets in a tree.  SIAM J. Algebraic Discrete Methods, 7(1):125–130, 1986.

Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic
---
Science (IBS), Daejeon, South Korea
Email address<EMAIL_ADDRESS>
School of Computing, Montana State University, Bozeman, MT, USA
Email address<EMAIL_ADDRESS>
Applied Mathematics, Illinois Institute of Technology, Chicago, IL, USA
Email address<EMAIL_ADDRESS>
Department of Mathematics, Uppsala University, Uppsala, Sweden
Email address<EMAIL_ADDRESS>
Department of Mathematics, Rutgers University, Piscataway, NJ, USA
Email address<EMAIL_ADDRESS>