# Distribution of zeros of matching polynomials
of hypergraphs

Jiang-Chao Wan, Yi Wang, Yi-zheng Fan  Center for Pure Mathematics, School of
Mathematical Sciences,
Anhui University, Hefei 230601, Anhui, China<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Let $\mathcal{H}$ be a connected $k$-graph with maximum degree ${\Delta}\geq
2$ and let $\mu(\mathcal{H},x)$ be the matching polynomial of $\mathcal{H}$.
In this paper, we focus on studying the distribution of zeros of the matching
polynomials of $k$-graphs. We prove that the zeros (with multiplicities) of
$\mu(\mathcal{H},x)$ are invariant under a rotation of an angle $2\pi/{\ell}$
in the complex plane for some positive integer $\ell$ and $k$ is the maximum
integer with this property. Let $\lambda(\mathcal{H})$ denote the maximum
modulus of all zeros of $\mu(\mathcal{H},x)$. We show that
$\lambda(\mathcal{H})$ is a simple root of $\mu(\mathcal{H},x)$ and

$\Delta^{1\over
k}\leq\lambda(\mathcal{H})<\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over
k}.$

To achieve these, we introduce the path tree $\mathcal{T}(\mathcal{H},u)$ of
$\mathcal{H}$ with respect to a vertex $u$ of $\mathcal{H}$, which is a
$k$-tree, and prove that

$\frac{\mu(\mathcal{H}-u,x)}{\mu(\mathcal{H},x)}=\frac{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}{\mu(\mathcal{T}(\mathcal{H},u),x)},$

which generalizes the celebrated Godsil’s identity on the matching polynomial
of graphs.

###### Key words and phrases:

Matching polynomial; Hypergraph; Path tree; Distribution of zeros

Corresponding author. Yi Wang

Funding. Supported by the National Natural Science Foundation of China (No.
12171002)

##  1\. Introduction

###  1.1. Background

There are several polynomials associated with a hypergraph, such as Tutte
polynomial [26, 27], the chromatic polynomial [46, 49], the characteristic
polynomial [8], and the matching polynomial [7, 45, 50]. One of the most
fundamental topics in hypergraph polynomial theory is to investigate the
distribution of zeros of these polynomials. Further results on the location of
zeros of graph polynomials can be found in [38, 43]. In this paper, we study
the distribution of zeros of the matching polynomials of hypergraphs.

A $k$-uniform hypergraph $\mathcal{H}=(V(\mathcal{H}),E(\mathcal{H}))$
consists of a vertex set $V(\mathcal{H})$ and an edge set $E(\mathcal{H})$,
where each $e\in E(\mathcal{H})$ is a $k$-element subset of $V(\mathcal{H})$.
In this paper, we use the term “$k$-graph” for the case of $k$-uniform
hypergraphs with $k\geq 2$, and the term “graph” exclusively for $k=2$. For a
subset $M$ of $E(\mathcal{H})$, denote by $V(M)$ the set of vertices of
$\mathcal{H}$ contained in an edge in $M$. If no two distinct edges in $M$
share a common vertex, then $M$ is called a matching of $\mathcal{H}$. The
maximum number of edges in a matching of $\mathcal{H}$ is called the matching
number of $\mathcal{H}$, denoted by $m(\mathcal{H})$. An $r$-matching is a
matching of size $r$. We denote by $p(\mathcal{H},r)$ the number of
$r$-matchings of $\mathcal{H}$, with the convention that $p(\mathcal{H},0)=1$.

Recently, to investigate the spectral radius of adjacency tensor of $k$-trees,
Su, Kang, Li, and Shan [45] introduced the following matching polynomial of a
$k$-graph $\mathcal{H}$:

(1.1) $\displaystyle\mu(\mathcal{H},x)=\sum_{r\geq
0}(-1)^{r}p(\mathcal{H},r)x^{|V(\mathcal{H})|-kr},$

which is a minor adjustment based on the definition of matching polynomial
introduced by Zhang, Kang, Shan and Bai [50], and Clark and Cooper [7].
However, most of their results are focused on the spectra of adjacency tensor
of $k$-trees but not on the properties of the matching polynomial itself. This
prompts us to explore more useful and interesting properties of the matching
polynomial.

When $k=2$ in (1.1), it is exactly the classical matching polynomial of a
graph introduced by Heilmann and Lieb [24]. The matching polynomial is an
important mathematical object and has been applied in different fields
including spectral graph theory [10, 18, 35, 39], combinatorics [5, 17],
statistical physics [23, 24], chemistry [1, 4, 20], and many others. We refer
readers to the textbooks [19, 34] for more background and history on the
matching polynomial theory, and see [38, 43] for related graph polynomials.

There are two fundamental theorems in matching polynomial theory mentioned
here. The first one is Theorem 1.1, proved independently by Mowshowitz [40,
Theorem 4] in 1972 and by Lovász and Pelikán [35, Theorem 1] in 1973,
indicates that the characteristic polynomial and the matching polynomial are
closely related. By applying this theorem, Mowshowitz [40] showed that there
exist infinitely many pairs of non-isomorphic cospectral trees, and Schwenk
[42] proved that almost all trees are not determined by their spectra.

######  Theorem 1.1 ([35, 40]).

The characteristic polynomial of a tree coincides with its matching
polynomial.

The other one is the following celebrated Heilmann-Lieb theorem [24], which
gives a characterization of distribution of zeros of matching polynomials of
graphs.

######  Theorem 1.2 (Heilmann–Lieb [24]).

Let $G$ be a graph with maximum degree $\Delta(G)\geq 2$. Then the zeros (with
multiplicities) of $\mu(G,x)$ are symmetrically distributed about the origin,
and lie in the interval
$\big{(}-2\sqrt{{\Delta(G)}-1},2\sqrt{{\Delta(G)}-1}\big{)}$.

The bound $2\sqrt{{\Delta(G)}-1}$ for zeros of matching polynomial of graphs
in Theorem 1.2 is closely related to the second largest eigenvalues of graphs.
If $G$ is a $d$-regular graph, then $d$ is always the largest adjacency
eigenvalue of $G$, called the trivial eigenvalue of $G$. The well known
Alon–Boppana Theorem [2] states that for every $d\geq 2$ and $\varepsilon>0$,
there are only finitely many $d$-regular graphs whose second largest
eigenvalue is at most $2\sqrt{d-1}-\varepsilon$. In addition, Friedman [14]
proved that for every $\varepsilon>0$, with high probability, random
$d$-regular graphs have second largest eigenvalue smaller than
$2\sqrt{d-1}+\varepsilon$, which was conjectured by Alon [2]. Motivated by the
above results, Lubotzky, Phillips, and Sarnark [37] introduced the concept of
Ramanujan graphs: $d$-regular graphs whose nontrivial eigenvalues are between
$-2\sqrt{d-1}$ and $2\sqrt{d-1}$. It plays an important role in the study of
linear expander of graphs [25]. Based on the upper bound in Theorem 1.2,
Marcus, Spielman, and Srivastava [39] showed that there are infinitely many
bipartite Ramanujan graphs by the breakthough technique called interlacing
family. See [22, 39] for more details and related topics.

Over the years, several different proofs of real-rootedness of the matching
polynomial in Theorem 1.2 were presented, see e.g. [6, 16, 19, 30]. It is
worth mentioning that the original proofs of Theorem 1.1 in [35] and 1.2 in
[24] are elementary, relying only on simple recurrence formulas for the
matching polynomial. One of essential reasons is that the zeros of the
matching polynomial of a graph are all real, and hence many methods in real-
rooted polynomial theory can be applied. However, as we show in this paper,
the matching polynomial of a $k$-graph must contain some nonreal zeros when
$k\geq 3$. Therefore, some of previous techniques for studying the matching
polynomial of a graph can’t be adapted to the $k$-graph setting.

###  1.2. Our results

Inspired by the above classical results on the matching polynomial of graphs
and lack of study of the matching polynomial of $k$-graphs, in this paper, we
investigate the distribution of zeros of the matching polynomial of
$k$-graphs. For the sake of convenience, we use $\lambda(\mathcal{H})$ to
denote the maximum modulus of all zeros of $\mu(\mathcal{H},x)$. Our first
result in this paper is the following theorem which can be viewed as a
generalization of Theorem 1.1 for $k$-graphs.

######  Theorem 1.3.

Let $\mathcal{T}$ be a $k$-tree. Then every zero of $\mu(\mathcal{T},x)$ is an
eigenvalue of the adjacency tensor of $\mathcal{T}$. Moreover,
$\lambda(\mathcal{T})$ is a root of $\mu(\mathcal{T},x)$ and equals to the
spectral radius of the adjacency tensor of $\mathcal{T}$.

Theorem 1.3 establishes a relation between the zeros of the matching
polynomial of a $k$-tree $\mathcal{T}$ and the eigenvalues of the adjacency
tensor of $\mathcal{T}$. In particular, it implies that we may study
$\lambda(\mathcal{T})$ in terms of the spectral radius of the adjacency tensor
of $\mathcal{T}$, and vice versa. In addition to its own conclusion, Theorem
1.3 plays an important role in the proof of our main result. To state the main
result, we need to introduce more notations. A real polynomial $f(x)$ is
called $\ell$-symmetric if

(1.2) $f(x)=x^{t}g(x^{\ell})$

for some nonnegative integer $t$ and some real polynomial $g(x)$. In other
words, $f(x)$ is $\ell$-symmetric if and only if its zeros remains invariant
under a rotation of an angle $2\pi/\ell$ on the complex plane. The maximum
number $\ell$ such that (1.2) holds is called the cyclic index of $f(x)$. Now,
Theorem 1.2 implies that for a graph $G$ with $\Delta(G)\geq 2$, the cyclic
index of $\mu(G,x)$ is $2$ and $\lambda(G)\leq 2\sqrt{{\Delta(G)}-1}$.

We are now ready to state our main result.

######  Theorem 1.4.

Let $\mathcal{H}$ be a connected $k$-graph with maximum degree ${\Delta}\geq
2$. Then the cyclic index of $\mu(\mathcal{H},x)$ is $k$,
$\lambda(\mathcal{H})$ is a simple root of $\mu(\mathcal{H},x)$, and

(1.3) $\Delta^{1\over
k}\leq\lambda(\mathcal{H})<\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over
k}.$

Theorem 1.4 extends Theorem 1.2 to $k$-graphs and provides a characterization
of distribution of zeros of matching polynomials of $k$-graphs. In particular,
it implies that the matching polynomial of a $k$-graph must contain some
nonreal zeros when $k\geq 3$.

The second eigenvalue of hypergraphs was introduced by Friedman and Wigderson
[12, 13]. Lenz and Mubayi [29] showed that a hypergraph satisfies some
quasirandom properties if and only if it has a small second eigenvalue. In
2019, Li and Mohar [31] generalized Alon–Boppana Theorem to $k$-graphs, and
showed that for any finite $d$-regular $k$-graph $\mathcal{H}$ on $n$
vertices, the second eigenvalue of $\mathcal{H}$ is at least

$\frac{k}{k-1}\big{(}(k-1)(d-1)\big{)}^{1\over k}-o_{n}(1),$

where $o_{n}(1)$ is a quantity that tends to zero for every fixed $d$ as
$n\rightarrow\infty$. Similar to the important application of Theorem 1.2 in
Ramanujan graphs, Theorem 1.4 is expected to be useful to extend Ramanujan
graphs to hypergraphs.

Moreover, combining Theorem 1.3 and Theorem 1.4, we immediately obtain the
following result due to Friedman [12](see also [31] by Li and Mohar).

######  Theorem 1.5 ([12, 31]).

Let $\mathcal{T}$ be a connected $k$-tree with maximum degree
$\mathnormal{\Delta}\geq 2$. Let $\rho(\mathcal{T})$ be the spectral radius of
the adjacency tensor of $\mathcal{T}$. Then

$\rho(\mathcal{T})<\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}.$

###  1.3. Methods and tools

In this subsection, we briefly describe the main methods and tools to be
applied in the proof of our theorems.

Recursive formula. One fundamental method in graph polynomial theory is to use
several types of recursive formulas, such as vertex-deletion or edge-deletion
recursive formula (see [15, 24, 38, 43]). The matching polynomial of a
$k$-graph still obeys the vertex-deletion recursive formula, see [45] or Lemma
2.6, and the recursive formula is crucial when we use mathematical induction
to obtain some properties of the matching polynomial.

The $\alpha$-normal method. In 2016, Lu and Man [36] introduced the
$\alpha$-normal method to investigate the spectral radii of $k$-graphs, which
is very powerful to deal with the eigenvalues of tensor [3, 50] and the
$p$-spectral radii of $k$-graphs [33]. Informally, the method transforms the
eigenvalue problem of the adjacency tensor of a $k$-graph $\mathcal{H}$ to the
problem of weighted incidence matrix of $\mathcal{H}$ with certain
restriction, which is easier to deal with especially for $k$-trees, see
Section 3 for details. We will use this method to prove Theorem 1.3 with some
additional techniques.

The path tree. The path tree (also called Godsil’s tree), introduced by Godsil
[15], is considered as one of the most important and useful tools in matching
polynomial theory. For a connected graph $G$ and a vertex $u\in V(G)$, the
path tree $T(G,u)$ is a tree which has vertices as the paths in $G$ starting
at $u$, where two such paths are adjacent if one is a maximal proper subpath
of the other. Godsil [15, Theorem 2.5] proved the following celebrated
identity:

(1.4) $\frac{\mu(G-u,x)}{\mu(G,x)}=\frac{\mu(T(G,u)-u,x)}{\mu(T(G,u),x)},$

and further that $\mu(G,x)$ divides $\mu(T(G,u),x)$. As mentioned above, some
of the previous proof-method in matching polynomial theory of graphs are
ineffective for $k$-graphs. However, it is surprising that we can generalize
the path tree from graphs to hypergraphs and prove that (1.4) is also true in
the $k$-graph paradigm. This is the essential tool of the paper, especially
for the proof of Theorem 1.4.

###  1.4. Organization of the paper

In Section 2, we introduce the path tree $\mathcal{T}(\mathcal{H},u)$ of a
$k$-graph $\mathcal{H}$ with respect to a vertex $u$, and prove that (1.4) is
also true in the $k$-graph paradigm. In Section 3, we prove Theorem 1.3 by
using the $\alpha$-normal method with some additional techniques. In Section
4, we investigate the distribution of zeros of the matching polynomial. Based
on (1.4) and Theorem 1.3, we prove that every zero of $\mu(\mathcal{H},x)$ is
an eigenvalue of the adjacency tensor of $\mathcal{T}(\mathcal{H},u)$, and the
cyclic index of $\mu(\mathcal{H},x)$ is $k$. Furthermore, we show that
$\lambda(\mathcal{H})$ is a simple root of $\mu(\mathcal{H},x)$, and is
exactly the spectral radius of the adjacency tensor of
$\mathcal{T}(\mathcal{H},u)$. Using these results, we establish the bounds
(1.3) of $\lambda(\mathcal{H})$ and prove Theorem 1.4 at the end of Section 4.
Finally, we conclude this paper with some further discssions and questions in
Section 5.

##  2\. Path trees of $k$-graphs

In order to prove Theorem 1.4, we introduce the path trees of $k$-graphs and
generalize the Godsil’s identity (1.4) to $k$-graphs. Before proceeding, we
introduce some notations and terminology. Let $v$ be a vertex of a $k$-graph
$\mathcal{H}$. Denote by $N_{\mathcal{H}}(v)$ the set of all vertices of
$\mathcal{H}$ adjacent to $v$ and by $E_{\mathcal{H}}(v)$ the set of all edges
of $\mathcal{H}$ incident with $v$. The degree of $v$ is defined as
$|E_{\mathcal{H}}(v)|$ and is denoted by $d_{\mathcal{H}}(v)$. The maximum
degree and minimum degree of the vertices of $\mathcal{H}$ is denoted by
$\Delta(\mathcal{H})$ and $\delta(\mathcal{H})$, respectively. For a subset
$W$ of $V(\mathcal{H})$, let $\mathcal{H}[W]$ denote the subgraph of
$\mathcal{H}$ induced by $W$, i.e., $V(\mathcal{H}[W])=W$ and
$E(\mathcal{H}[W])=\\{e\in E(\mathcal{H}):e\subset W\\}$. For the sake of
convenience, we simply write $\mathcal{H}-W$ instead of
$\mathcal{H}[V(\mathcal{H})\setminus W]$, write $\mathcal{H}-v$ for
$\mathcal{H}-\\{v\\}$, and use $\mathcal{H}-e$ to denote
$\mathcal{H}-\\{v_{1},\ldots,v_{k}\\}$ where $e=\\{v_{1},\ldots,v_{k}\\}$ is
an edge. Let $p=(v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{\ell},v_{\ell})$ be a
sequence of vertices and edges alternatively. $p$ is called a path in a
$k$-graph $\mathcal{H}$ if the vertices and edges are distinct and
${v_{i},v_{i+1}}\in e_{i+1}$ for $i=0,1,\ldots,\ell-1$. $p$ is called a cycle
if we only allow $v_{0}=v_{\ell}$ in the definition of the path.

######  Definition 2.1.

A path $p=(v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{\ell},v_{\ell})$ is said to
be nonbacktracking if $v_{i}\notin e_{j}$ for any $0\leq i<j-1\leq\ell-1$,
equivalently, for any $2\leq j\leq\ell$, $e_{j}$ contains no any vertex in the
set $\\{v_{0},v_{1},\ldots,v_{j-2}\\}$.

A $k$-graph $\mathcal{H}$ is connected if any pair of vertices of
$\mathcal{H}$ are connected by a path, and is a $k$-uniform hypertree (or
simply $k$-tree) if $\mathcal{H}$ is both connected and acyclic. In
particular, we say that $p$ begins at the vertex $v_{0}$ and terminates at the
vertex $v_{\ell}$ and the edge $e_{\ell}$. We use $v(p)$ and $e(p)$ to denote
the terminal vertex and the terminal edge of $p$, respectively. A path
$p^{\prime}$ is called a continuation of $p$ if it is lengthened from $p$ by
attaching a new edge at $v(p)$.

######  Definition 2.2.

Let $\mathcal{H}$ be a connected $k$-graph and $u$ be a vertex of
$\mathcal{H}$. The path tree $\mathcal{T}(\mathcal{H},u)$ with respect to $u$
is a $k$-graph whose vertices are all nonbacktracking paths in $\mathcal{H}$
starting at $u$ and $p_{1}$ and its continuations $p_{2},\ldots,p_{k}$ form an
edge of $\mathcal{T}(\mathcal{H},u)$ if and only if
$e(p_{2})=\cdots=e(p_{k})$.

######  Remark 2.3.

For $k=2$, a nonbacktracking path is just a path. Therefore, the path trees of
$k$-graphs is an extension of the path trees of graphs.

For a given vertex $u\in V(\mathcal{H})$, $u$ itself is a path, and the
corresponding vertex of $T(\mathcal{H},u)$ will be also referred to as $u$.
Observe that $\mathcal{T}(\mathcal{H},u)$ is determined by $\mathcal{H}$ and
$u$. Figure 2 shows an example of a path tree of the complete $3$-graph on
four vertices, depicted in Figure 1.

$e_{2}$$e_{1}$$e_{3}$$a$$b$$c$$d$ $V(K_{4}^{3})=\\{a,b,c,d\\}$
---
$E(K_{4}^{3})=\\{e_{1},e_{2},e_{3},e_{4}\\}$
$e_{1}=\\{a,b,d\\}$
$e_{2}=\\{a,c,d\\}$
$e_{3}=\\{b,c,d\\}$
$e_{4}=\\{a,b,c\\}$
Figure 1. The graph $K_{4}^{3}$.
$(a,e_{1},b,e_{3},c)$$(a,e_{1},b,e_{3},d)$$(a,e_{1},d,e_{3},b)$$(a,e_{1},d,e_{3},c)$$(a,e_{4},b,e_{3},c)$$(a,e_{4},b,e_{3},d)$$(a,e_{4},c,e_{3},b)$$(a,e_{4},c,e_{3},d)$$(a,e_{2},c,e_{3},b)$$(a,e_{2},c,e_{3},d)$$(a,e_{2},d,e_{3},b)$$(a,e_{2},d,e_{3},c)$$(a)$$(a,e_{4},b)$$(a,e_{4},c)$$(a,e_{1},b)$$(a,e_{1},d)$$(a,e_{2},c)$$(a,e_{2},d)$
Figure 2. The path tree $\mathcal{T}(K_{4}^{3},a)$.

Two $k$-graphs $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ are called isomorphic,
denoted by $\mathcal{H}_{1}\backsimeq\mathcal{H}_{2}$, if there exists a
bijection $\theta:V(\mathcal{H}_{1})\mapsto V(\mathcal{H}_{2})$ such that
$\\{v_{1},\ldots,v_{k}\\}\in E(\mathcal{H}_{1})$ if and only if
$\\{\theta(v_{1}),\ldots,\theta(v_{k})\\}\in E(\mathcal{H}_{2})$. We call such
bijection $\theta$ an isomorphism from $\mathcal{H}_{1}$ to $\mathcal{H}_{2}$.
The following lemma shows that a path tree is indeed a $k$-tree, and presents
some important properties of path trees which will be used in later.

######  Lemma 2.4.

Let $\mathcal{H}$ be a connected $k$-graph and $u$ be a vertex of
$\mathcal{H}$. Then we have the following:

  1. (1)

$\mathcal{T}(\mathcal{H},u)$ is a $k$-tree.

  2. (2)

$\mathcal{H}$ is a $k$-tree if and only if $\mathcal{T}(\mathcal{H},u)$ is
isomorphic to $\mathcal{H}$.

  3. (3)

Let $E_{\mathcal{H}}(u,v)=E_{\mathcal{H}}(u)\cap E_{\mathcal{H}}(v)$ and
$e_{\mathcal{H}}(u,v)=|E_{\mathcal{H}}(u,v)|$. Then

$\mathcal{T}(\mathcal{H},u)-u\backsimeq\bigoplus_{w\in
N_{\mathcal{H}}(u)}e_{\mathcal{H}}(u,w)\mathcal{T}(\mathcal{H}-u,w),$

where $\bigoplus$ denotes the distinct union of $k$-graphs and $t\mathcal{H}$
denotes the disjoint union of $t$ copies of $\mathcal{H}$.

###### Proof.

(1) For simplicity, denote $\mathcal{T}=\mathcal{T}(\mathcal{H},u)$. By the
definition of $\mathcal{T}$, $\mathcal{T}$ has no cycle. Since $\mathcal{T}$
is $k$-uniform and acyclic, it suffices to prove that $\mathcal{T}$ is
connected. We prove the connectedness recursively. Fix an arbitrary vertex
$p\in V(\mathcal{T})$. If $p^{\prime}$ is a continuation of $p$ with terminal
edge $e(p^{\prime})=\\{v(p),v(p^{\prime}),v_{3},\ldots,v_{k}\\}$, i.e.,
$e(p^{\prime})$ is the new added edge in $p^{\prime}$, by the property of
nonbacktracking paths of $p^{\prime}$, the nonbacktracking path
$(p,e(p^{\prime}),v_{i})$ is also a continuation of $p$ for every $3\leq i\leq
k$. Thus the set

$\\{p,p^{\prime},(p,e(p^{\prime}),v_{3}),\ldots,(p,e(p^{\prime}),v_{k})\\}$

forms an edge of $\mathcal{T}$. This implies the connectedness.

(2) If $\mathcal{H}$ is a $k$-tree, then there is a unique path joining $u$
and $v$ for each vertex $v\in V(\mathcal{H})$. Now, the mapping that maps each
vertex $v$ to the unique path joining $u$ to $v$ is an isomorphism from
$\mathcal{H}$ to $\mathcal{T}$. On the other hand, if $\mathcal{H}$ contains
some cycles, then $\mathcal{T}$ is not isomorphic to $\mathcal{H}$ since
$\mathcal{T}$ is a $k$-tree by (1).

(3) The last statement is straightforward from the definition of
$\mathcal{T}$. ∎

Let $\mathcal{H}$ be a $k$-graph with the components
$\mathcal{H}_{1},\ldots,\mathcal{H}_{s}$. For each $i=1,\ldots,s$, let
$\mathcal{T}(\mathcal{H}_{i},v_{i})$ be the path tree of $\mathcal{H}_{i}$
with respect to the vertex $v_{i}\in V(\mathcal{H}_{i})$. We can naturally
define the path tree of $\mathcal{H}$ with respect to
$\mathbf{v}=(v_{1},\ldots,v_{s})$ to be the disjoint union of
$\mathcal{T}(\mathcal{H}_{1},v_{1}),\ldots,\mathcal{T}(\mathcal{H}_{s},v_{s})$,
denoted by $\mathcal{T}(\mathcal{H},\mathbf{v})$. Note that

(2.1)
$\mu(\mathcal{H}_{1}\oplus\mathcal{H}_{2},x)=\mu(\mathcal{H}_{1},x)\mu(\mathcal{H}_{2},x)$

for disjoint union of $k$-graphs $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$, so
we usually restrict our attention to connected $k$-graphs.

If $\mathcal{H}$ is not connected, define
$\mathcal{T}(\mathcal{H},u)=\mathcal{T}(\widehat{\mathcal{H}},u)$, where
$\widehat{\mathcal{H}}$ is the component of $\mathcal{H}$ containing $u$.
Combining (2.1), we immediately obtain the following lemma, which will be used
to discuss the case for disconnected $k$-graphs.

######  Lemma 2.5.

Let $\mathcal{H}$ be a $k$-graph and $u\in V(\mathcal{H})$. Let
$\widehat{\mathcal{H}}$ be the component of $\mathcal{H}$ containing $u$. We
have the following:

(2.2)
$\frac{\mu(\mathcal{H}-u,x)}{\mu(\mathcal{H},x)}=\frac{\mu(\widehat{\mathcal{H}}-u,x)}{\mu(\widehat{\mathcal{H}},x)},$

and

(2.3)
$\frac{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}{\mu(\mathcal{T}(\mathcal{H},u),x)}=\frac{\mu(\mathcal{T}(\widehat{\mathcal{H}},u)-u,x)}{\mu(\mathcal{T}(\widehat{\mathcal{H}},u),x)}.$

To present the main results of this section, we also need the following lemma
that provides a recursive formula for the matching polynomial of $k$-graphs.

######  Lemma 2.6 ([45]).

Let $\mathcal{H}$ be a $k$-graph. For each vertex $u\in V(\mathcal{H})$,

$\mu(\mathcal{H},x)=x\mu(\mathcal{H}-u,x)-\sum_{e\in
E_{\mathcal{H}}(u)}\mu(\mathcal{H}-e,x).$

The following two theorems play a crucial role in this paper, and the case
$k=2$ was proved by Godsil (see [15, 16] or [19, Chapter 6]).

######  Theorem 2.7.

Let $\mathcal{H}$ be a $k$-graph. Then, for any vertex $u\in V(\mathcal{H})$,

(2.4)
$\frac{\mu(\mathcal{H}-u,x)}{\mu(\mathcal{H},x)}=\frac{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}{\mu(\mathcal{T}(\mathcal{H},u),x)}.$

###### Proof.

We prove (2.4) by induction on $|V(\mathcal{H})|$. If $|V(\mathcal{H})|=k$, we
can assume that $\mathcal{H}$ is a $k$-tree with a single edge, so (2.4) holds
by Lemma 2.4 (2).

Assume $|V(\mathcal{H})|>k$. For a given $e=\\{u,v_{2},\ldots,v_{k}\\}\in
E_{\mathcal{H}}(u)$, denote by

$p(e)=\\{(u),(u,e,v_{2}),\ldots,(u,e,v_{k})\\}$

the edge of $\mathcal{T}(\mathcal{H},u)$ corresponding to $e$. We first prove
the following claim.

Claim:

(2.5)
$\displaystyle\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}=\frac{\mu(\mathcal{T}(\mathcal{H},u)-p(e),x)}{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}.$

Proof of Claim: Let $V_{i}=\\{u,v_{2},\ldots,v_{i}\\}$ for each $i=2,\ldots,k$
and $V_{1}=\\{u\\}$. By the induction hypothesis and Lemma 2.5, we have

(2.6)
$\displaystyle\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}=\prod_{i=1}^{k-1}\frac{\mu(\mathcal{H}-V_{i+1},x)}{\mu(\mathcal{H}-V_{i},x)}=\prod_{i=1}^{k-1}\frac{\mu(\mathcal{T}(\mathcal{H}-V_{i},v_{i+1})-v_{i+1},x)}{\mu(\mathcal{T}(\mathcal{H}-V_{i},v_{i+1}),x)}.$

Here, $\mathcal{H}-V_{i}$ may be disconnected for some $i$, and in this case
we also obtain (2.6) by Lemma 2.5.

Let $p_{i}(e)=\\{(u),(u,e,v_{2}),\ldots,(u,e,v_{i})\\}$ for each
$i=2,\ldots,k$ and $p_{1}(e)=\\{u\\}$. Then,

(2.7)
$\displaystyle\frac{\mu(\mathcal{T}(\mathcal{H},u)-p(e),x)}{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}=\prod_{i=1}^{k-1}\frac{\mu(\mathcal{T}(\mathcal{H},u)-p_{i+1}(e),x)}{\mu(\mathcal{T}(\mathcal{H},u)-p_{i}(e),x)}.$

Combining (2.6) and (2.7), in order to prove (2.5), it suffices to show that

(2.8)
$\displaystyle\frac{\mu(\mathcal{T}(\mathcal{H}-V_{i},v_{i+1})-v_{i+1},x)}{\mu(\mathcal{T}(\mathcal{H}-V_{i},v_{i+1}),x)}=\frac{\mu(\mathcal{T}(\mathcal{H},u)-p_{i+1}(e),x)}{\mu(\mathcal{T}(\mathcal{H},u)-p_{i}(e),x)}$

for each $i=1,\ldots,k-1$. This fact follows from the observation that
$\mathcal{T}(\mathcal{H}-V_{i},v_{i+1})$ is isomorphic to the component of
$\mathcal{T}(\mathcal{H},u)-p_{i}(e)$ containing the path $(u,e,v_{i+1})$ as a
vertex. This proves the claim.

By Lemma 2.6 and (2.5), one can deduce that

$\displaystyle\frac{\mu(\mathcal{H},x)}{\mu(\mathcal{H}-u,x)}=$
$\displaystyle\frac{x\mu(\mathcal{H}-u,x)-\sum_{e\in
E_{\mathcal{H}}(u)}\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}$ (by Lemma 2.6)
$\displaystyle=$ $\displaystyle x-\sum_{e\in
E_{\mathcal{H}}(u)}\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}$
$\displaystyle=$ $\displaystyle x-\sum_{e\in
E_{\mathcal{H}}(u)}\frac{\mu(\mathcal{T}(\mathcal{H},u)-p(e),x)}{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}$
(by (2.5)) $\displaystyle=$ $\displaystyle x-\sum_{p\in
E_{\mathcal{T}(\mathcal{H},u)}(u)}\frac{\mu(\mathcal{T}(\mathcal{H},u)-p,x)}{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}$
$\displaystyle=$
$\displaystyle\frac{x\mu(\mathcal{T}(\mathcal{H},u)-u,x)-\sum_{p\in
E_{\mathcal{T}(\mathcal{H},u)}(u)}\mu(\mathcal{T}(\mathcal{H},u)-p,x)}{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}$
$\displaystyle=$
$\displaystyle\frac{\mu(\mathcal{T}(\mathcal{H},u),x)}{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}.$
(by Lemma 2.6)

This completes the proof of the theorem. ∎

######  Theorem 2.8.

Let $\mathcal{H}$ be a $k$-graph and $u\in V(\mathcal{H})$. Then there exists
a proper subforest $\mathcal{F}$ of $\mathcal{T}(\mathcal{H},u)$ such that

$\mu(\mathcal{H},x)=\frac{\mu(\mathcal{T}(\mathcal{H},u),x)}{\mu(\mathcal{F},x)}.$

In particular, $\mu(\mathcal{H},x)$ divides
$\mu(\mathcal{T}(\mathcal{H},u),x)$.

###### Proof.

We prove the first statement by induction on $|V(\mathcal{H})|$. It is trivial
for the case $|V(\mathcal{H})|=k$ by Lemma 2.4 (2).

Assume $|V(\mathcal{H})|>k$. By Theorem 2.7, we have

(2.9)
${\mu(\mathcal{T}(\mathcal{H},u),x)}={\mu(\mathcal{H},x)}\frac{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}{\mu(\mathcal{H}-u,x)}.$

Thus, to prove the first statement, it suffices to prove that the second
factor on the right side of (2.9) is a matching polynomial of a subforest of
$\mathcal{T}(\mathcal{H},u)$. Let $\mathcal{H}_{1},\ldots,\mathcal{H}_{s}$ be
the components of $\mathcal{H}-u$. Then,

$\mu(\mathcal{H}-u,x)=\prod_{i=1}^{s}\mu(\mathcal{H}_{i},x).$

Let $w_{i}\in V(\mathcal{H}_{i})$ be a nieghbor of $u$ in $\mathcal{H}$ for
each $i=1,\ldots,s$, and let $W=\\{w_{1},\ldots,w_{s}\\}$. By Lemma 2.4 (3),
we have

$\displaystyle\mu(\mathcal{T}(\mathcal{H},u)-u,x)=$ $\displaystyle\prod_{w\in
N_{\mathcal{H}}(u)}\Big{(}\mu(\mathcal{T}(\mathcal{H}-u,w),x)\Big{)}^{e_{\mathcal{H}}(u,w)}$
$\displaystyle=$
$\displaystyle\left(\prod_{i=1}^{s}\Big{(}\mu(\mathcal{T}(\mathcal{H}-u,w_{i}),x)\Big{)}^{e_{\mathcal{H}}(u,w_{i})}\right)\left(\prod_{w\in
N_{\mathcal{H}}(u)\setminus
W}\Big{(}\mu(\mathcal{T}(\mathcal{H}-u,w),x)\Big{)}^{e_{\mathcal{H}}(u,w)}\right)$
$\displaystyle=$
$\displaystyle\mu(\widehat{\mathcal{H}},x)\left(\prod_{i=1}^{s}\mu(\mathcal{T}(\mathcal{H}-u,w_{i}),x)\right),$

where

$\displaystyle\widehat{\mathcal{H}}=\left(\bigoplus_{i=1}^{s}(e_{\mathcal{H}}(u,w_{i})-1)\mathcal{T}(\mathcal{H}-u,w_{i})\right)\oplus\left(\bigoplus_{w\in
N_{\mathcal{H}}(u)\setminus
W}e_{\mathcal{H}}(u,w)\mathcal{T}(\mathcal{H}-u,w)\right).$

Therefore,

$\frac{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}{\mu(\mathcal{H}-u,x)}=\mu(\widehat{\mathcal{H}},x)\left(\prod_{i=1}^{s}\frac{\mu(\mathcal{T}(\mathcal{H}-u,w_{i}),x)}{\mu(\mathcal{H}_{i},x)}\right).$

Since $\mathcal{T}(\mathcal{H}-u,w_{i})$ is a path tree of $\mathcal{H}_{i}$,
by induction hypothesis, for each $i=1,\ldots,s$, there exists subforest
$F_{i}$ of $\mathcal{T}(\mathcal{H}-u,w_{i})$ such that

$\mu(F_{i},x)=\frac{\mu(\mathcal{T}(\mathcal{H}-u,w_{i}),x)}{\mu(\mathcal{H}_{i},x)}.$

Thus,

$\frac{\mu(\mathcal{T}(\mathcal{H},u)-u,x)}{\mu(\mathcal{H}-u,x)}=\mu(\widehat{\mathcal{H}},x)\left(\prod_{i=1}^{s}\mu(F_{i},x)\right).$

Moreover, one can directly check that
$\Big{(}\bigoplus_{i=1}^{s}F_{i}\Big{)}\bigoplus\widehat{\mathcal{H}}$ is a
proper subforest of $\mathcal{T}(\mathcal{H},u)$ and this implies the first
statement. The ‘in particular’ statement easily follows from the first
statement. ∎

##  3\. Zeros of matching polynomials of $k$-trees

The aim of this section is to prove Theorem 1.3. We begin with the notations
of eigenvalues of tensor and the $\alpha$-normal method.

###  3.1. Eigenvalues of the adjacency tensor of $k$-graphs

A real tensor (also called _hypermatrix_) $\mathcal{A}=(a_{i_{1}\ldots
i_{k}})$ of order $k$ and dimension $n$ refers to a multi-dimensional array
with entries $a_{i_{1}\ldots i_{k}}\in\mathbb{R}$ for all
$i_{j}\in[n]=\\{1,\ldots,n\\}$ and $j\in[k]$. Clearly, if $k=2$, then
$\mathcal{A}$ is a square matrix of dimension $n$. Let
$\mathcal{I}=(\iota_{i_{1}\ldots i_{k}})$ be the identity tensor of order $k$
and dimension $n$, that is, $\iota_{i_{1}\ldots i_{k}}=1$ if
$i_{1}=\cdots=i_{k}\in[n]$ and $\iota_{i_{1}\ldots i_{k}}=0$ otherwise.

Let $\mathcal{A}=(a_{i_{1}\ldots i_{k}})$ be a tensor of order $k$ and
dimension $n$. For a vector
$\mathbf{x}=(\mathbf{x}_{1},\ldots,\mathbf{x}_{n})^{\top}\in\mathbb{C}^{n}$,
denote by
$\mathbf{x}^{[k]}=(\mathbf{x}_{1}^{k},\ldots,\mathbf{x}_{n}^{k})^{\top}$ and
let $\mathcal{A}\mathbf{x}^{k-1}$ be a vector in $\mathbb{C}^{n}$ whose $i$th
component is defined in the following

$\displaystyle(\mathcal{A}\mathbf{x}^{k-1})_{i}$
$\displaystyle=\sum_{i_{2},\ldots,i_{k}\in[n]}a_{ii_{2}\ldots
i_{k}}\mathbf{x}_{i_{2}}\cdots\mathbf{x}_{i_{k}}.$

In 2005, Lim [32] and Qi [41] independently introduced the eigenvalues of
tensors. For some $\lambda\in\mathbb{C}$, if the polynomial system

$\mathcal{A}\mathbf{x}^{k-1}=\lambda\mathbf{x}^{[k-1]},$

has a solution $\mathbf{x}\in\mathbb{C}^{n}\backslash\\{0\\}$, then $\lambda$
is called an _eigenvalue_ of $\mathcal{A}$ and $\mathbf{x}$ is an
_eigenvector_ of $\mathcal{A}$ associated with $\lambda$.

The _determinant_ of $\mathcal{A}$, denoted by $\det\mathcal{A}$, is defined
as the resultant of the polynomial system $\mathcal{A}\mathbf{x}^{k-1}$ [21]
and the _characteristic polynomial_ $\phi_{\mathcal{A}}(x)$ of $\mathcal{A}$
is defined as $\det(x\mathcal{I}-\mathcal{A})$ [41]. It is proved in [41] that
$\lambda$ is an eigenvalue of $\mathcal{A}$ if and only if it is a root of
$\varphi_{\mathcal{A}}(x)$.

Let $\mathcal{H}$ be a $k$-graph on $n$ vertices $v_{1},\ldots,v_{n}$. The
adjacency tensor of $\mathcal{H}$ [8] is defined as
$\mathcal{A}(\mathcal{H})=(a_{i_{1}\ldots i_{k}})$, an order $k$
$n$-dimensional tensor, where

$a_{i_{1}i_{2}\ldots
i_{k}}=\left\\{\begin{array}[]{ll}\frac{1}{(k-1)!},&\mbox{if\leavevmode\nobreak\
}\\{v_{i_{1}},\ldots,v_{i_{k}}\\}\in E(\mathcal{H});\\\
0,&\mbox{otherwise}.\end{array}\right.$

In this paper, the eigenvalues of a $k$-graph $\mathcal{H}$ always refer to
those of its adjacency tensor. The spectral radius of $\mathcal{H}$ is defined
as

$\rho(\mathcal{H})=\max\\{|\lambda|:\lambda\mbox{ is an eigenvalue of
}\mathcal{A}(\mathcal{H})\\},$

which is exactly the spectral radius of $\mathcal{A}(\mathcal{H})$.

The next two lemmas are the applications of the Perron–Frobenius theorem of
weakly irreducible nonnegative tensors [11, 47, 48].

######  Lemma 3.1 ([8, 28]).

Let $\mathcal{H}$ be a connected $k$-graph. Then $\rho(\mathcal{H})$ is an
eigenvalue of $\mathcal{A}(\mathcal{H})$ with an corresponding eigenvector
having all elements positive, and $\rho(\mathcal{G})<\rho(\mathcal{H})$ for
any proper subgraph $\mathcal{G}$ of $\mathcal{H}$.

We use $H\setminus e$ to denote the $k$-graph obtained from $H$ by deleting
$e$ along with resultant isolated vertices.

######  Lemma 3.2 (Theorem 13, [51]).

Let $\mathcal{H}$ be a $k$-graph and $e\in E(\mathcal{H})$ be an edge
containing two degree-one vertices. If $\lambda$ is an eigenvalue of
$\mathcal{A}(\mathcal{H}\setminus e)$, then $\lambda$ is an eigenvalue of
$\mathcal{A}(\mathcal{H})$.

An edge $e$ of $\mathcal{H}$ is called a pendent edge if it contains exactly
$k-1$ vertices of degree one. If $\mathcal{F}$ is a subtree of a $k$-tree
$\mathcal{T}$, it is known in [7] that there exists a sequence of edges
$(e_{1},\ldots,e_{s})$ such that, for any $i$ $(1\leq i\leq s)$, $e_{i}$ is a
pendant edge of $\mathcal{T}_{i-1}$, where $\mathcal{T}_{0}=\mathcal{T}$,
$\mathcal{T}_{i}=\mathcal{T}_{i-1}\setminus e_{i}$, and
$\mathcal{T}_{s}=\mathcal{F}$. From this fact and Lemma 3.2, we immediately
obtain the following result.

######  Corollary 3.3.

If $\mathcal{F}$ is a subtree of a $k$-tree $\mathcal{T}$, then every
eigenvalue of $\mathcal{A}(\mathcal{F})$ is an eigenvalue of
$\mathcal{A}(\mathcal{T})$.

###  3.2. The $\alpha$-normal method for $k$-graphs

In 2016, Lu and Man [36] introduced the $\alpha$-normal method to investigate
the spectral radii of $k$-graphs. The method is a powerful tool to deal with
the eigenvalues of tensor [3, 50] and the $p$-spectral radii of $k$-graphs
[33].

Let $\mathcal{H}$ be a $k$-graph. A weighted incidence matrix $B$ of
$\mathcal{H}$ is a complex matrix whose rows are indexed by $V(\mathcal{H})$
and columns are indexed by $E(\mathcal{H})$ such that for any $v\in
V(\mathcal{H})$ and any $e\in E(\mathcal{H})$, the entry $B(v,e)\neq 0$ if and
only if $v\in e$.

######  Definition 3.4 ([50]).

Let $\mathcal{H}$ be a $k$-graph, and let $\\{\alpha_{e}\\}_{e\in
E(\mathcal{H})}$ be an ordered sequence consisting of complex numbers such
that $\alpha_{e}\neq 0$ for any $e\in E(\mathcal{H})$. We call $\mathcal{H}$
generalized $\\{\alpha_{e}\\}_{e\in E(\mathcal{H})}$-normal with respect to
$B$ if there exists a weighted incidence matrix $B$ of $\mathcal{H}$ such that

  1. (C1)

$\sum\limits_{e\in E_{\mathcal{H}}(v)}B(v,e)=1$ for any $v\in V(\mathcal{H})$.

  2. (C2)

$\prod\limits_{v\in e}B(v,e)=\alpha_{e}$ for any $e\in E(\mathcal{H})$.

If $\alpha_{e}=\alpha$ for any $e\in E(\mathcal{H})$, then $\mathcal{H}$ is
called generalized $\alpha$-normal. Moreover, $\mathcal{H}$ is called
consistently generalized $\alpha$-normal with respect to $B$ if $\mathcal{H}$
is generalized $\alpha$-normal and

  1. (C3)

For any cycle $v_{0}e_{1}v_{1}\cdots e_{\ell}v_{\ell}(=v_{0})$ of
$\mathcal{H}$,

$\prod_{i=1}^{\ell}\frac{B(v_{i},e_{i})}{B(v_{i-1},e_{i})}=1.$

In what follows, we simply say that $\mathcal{H}$ is generalized
$\\{\alpha_{e}\\}_{e\in E(\mathcal{H})}$-normal or generalized $\alpha$-normal
if the weighted incidence matrix $B$ is clear from the context.

######  Lemma 3.5 (Lemma 2.2, [50]).

Let $\mathcal{H}$ be a connected $k$-graph. Then, a nonzero number $\lambda$
is an eigenvalue of $\mathcal{H}$ corresponding to an eigenvector with all the
elements nonzero if and only if $\mathcal{H}$ is consistently generalized
$\alpha$-normal with $\alpha=\lambda^{-k}$.

###  3.3. Proof of Theorem 1.3

This subsection is devoted to proving Theorem 1.3. For this, let us first
introduce some more notations and terminology which we need. Let $\mathcal{T}$
be a $k$-forest and $\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in
E(\mathcal{T})}\right)$ denote the following multivariate polynomial with
respect to indeterminates $\\{x_{e}\\}_{e\in E(\mathcal{T})}$:

(3.1) $\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in
E(\mathcal{T})}\right)=\sum_{M\in\mathcal{M}(\mathcal{T})}(-1)^{|M|}\prod_{e\in
E(M)}x_{e}.$

If $\Delta(\mathcal{T})\geq 2$, then there exists a vertex $u$ such that
$d_{\mathcal{T}}(u)\geq 2$ and it is incident with at most one non-pendent
edge in $\mathcal{T}$. Denote by $\mathcal{N}(\mathcal{T})$ all such vertices
of $\mathcal{T}$. Take a vertex $u\in\mathcal{N}(\mathcal{T})$. Denote by
$P_{\mathcal{T}}(u)$ the set consisting of $d_{\mathcal{T}}(u)-1$ chosen
pendent edges incident to $u$, and denote by $f$ the remaining edge incident
to $u$. Let $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ be an ordered sequence
consisting of nonzero complex numbers. The triple
$(\mathcal{T},u,P_{\mathcal{T}}(u))$ is called admissible with respect to
$\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ if

$\sum_{g\in P_{\mathcal{T}}(u)}\alpha_{g}\neq 1.$

Otherwise, it is called inadmissible.

The following result suggests that if a $k$-tree $\mathcal{T}$ and a sequence
$\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ satisfy some restrictions, then the
‘root’ of $\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in
E(\mathcal{T})}\right)$ and the ‘generalized $\\{\alpha_{e}\\}_{e\in
E(\mathcal{T})}$-normal’ of $\mathcal{T}$ obey a recursive rule. It is
noticeable that the proof idea of the following result derives from the proof
of [50, Theorem 3.1].

######  Lemma 3.6.

Let $\mathcal{T}$ be a $k$-tree with $\Delta(\mathcal{T})\geq 2$ and
$\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ be an order sequence consisting of
nonzero complex numbers. Assume that $(\mathcal{T},u,P_{\mathcal{T}}(u))$ is
admissible with respect to $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$. Let
$\widehat{\mathcal{T}}$ be the $k$-forest obtained from $\mathcal{T}$ by
deleting all edges in $P_{\mathcal{T}}(u)$ and the resultant isolated
vertices. Set $\widehat{\alpha}_{e}=\alpha_{e}$ for any $e\in
E(\widehat{\mathcal{T}})\setminus\\{f\\}$ and
$\widehat{\alpha}_{f}=\frac{\alpha_{f}}{1-\sum\limits_{g\in
P_{\mathcal{T}}(u)}\alpha_{g}}.$ Then the following assertions hold.

  1. (1)

If $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ is a root of
$\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in E(\mathcal{T})}\right)$,
then $\\{\widehat{\alpha}_{e}\\}_{e\in E(\widehat{\mathcal{T}})}$ is a root of
$\widetilde{\mu}\left(\widehat{\mathcal{T}},\\{x_{e}\\}_{e\in
E(\widehat{\mathcal{T}})}\right)$.

  2. (2)

If $\widehat{\mathcal{T}}$ is generalized $\\{\widehat{\alpha}_{e}\\}_{e\in
E(\widehat{\mathcal{T}})}$-normal, then $\mathcal{T}$ is generalized
$\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$-normal.

###### Proof.

(1). Assume that $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ is a root of
$\widetilde{\mu}(\mathcal{T},\\{x_{e}\\}_{e\in E(\mathcal{T})})$, and write
$\chi_{M}=\prod_{e\in E(M)}\alpha_{e}$ for any matching $M$ of $\mathcal{T}$.
Then we have

(3.2)
$\sum_{M\in\mathcal{R}}(-1)^{|M|}\chi_{M}+\sum_{M\in\mathcal{S}}(-1)^{|M|}\chi_{M}+\sum_{M\in\mathcal{M}(T)\setminus(\mathcal{R}\cup\mathcal{S})}(-1)^{|M|}\chi_{M}=0,$

where $\mathcal{R}$ is the set of all matchings of $\mathcal{T}$ containing
$f$, and $\mathcal{S}$ is the set of all matchings of $\mathcal{T}$ containing
none of edges incident to $u$ in $\mathcal{T}$. Moreover, (3.2) is equivalent
to

(3.3)
$\sum_{M\in\mathcal{R}(\widehat{\mathcal{T}})}(-1)^{|M|}\chi_{M}+\sum_{M\in\mathcal{S}(\widehat{\mathcal{T}})}(-1)^{|M|}\chi_{M}-\left(\sum\limits_{g\in
P_{\mathcal{T}}(u)}\chi_{g}\right)\left(\sum_{M\in\mathcal{S}(\widehat{\mathcal{T}})}(-1)^{|M|}\chi_{M}\right)=0,$

where $\mathcal{R}(\widehat{\mathcal{T}})$ is the set of all matchings of
$\widehat{T}$ containing $f$, and
$\mathcal{S}(\widehat{\mathcal{T}})=\mathcal{M}(\widehat{\mathcal{T}})\setminus\mathcal{R}(\widehat{\mathcal{T}})$.
Rearranging (3.3), we have

(3.4)
$\sum_{M\in\mathcal{R}(\widehat{T})}(-1)^{|M|}\chi_{M}+\left(1-\sum\limits_{g\in
P_{\mathcal{T}}(u)}\alpha_{g}\right)\sum_{M\in\mathcal{S}(\widehat{T})}(-1)^{|M|}\chi_{M}=0.$

Note that $\sum_{g\in P_{\mathcal{T}}(u)}\alpha_{g}\neq 1,$ so (3.4) is
equivalent to say that

(3.5)
$\sum_{M\in\mathcal{R}(\widehat{T})}(-1)^{|M|}\left(\frac{1}{1-\sum\limits_{g\in
P_{\mathcal{T}}(u)}\alpha_{g}}\prod_{e\in
E(M)}\alpha_{e}\right)+\sum_{M\in\mathcal{S}(\widehat{T})}(-1)^{|M|}\chi_{M}=0.$

This implies that $\\{\widehat{\alpha}_{e}\\}_{e\in E(\widehat{\mathcal{T}})}$
is a root of $\widetilde{\mu}\left(\widehat{\mathcal{T}},\\{x_{e}\\}_{e\in
E(\widehat{\mathcal{T}})}\right)$, as desired.

(2). Assume that $\widehat{\mathcal{T}}$ is generalized
$\\{\widehat{\alpha}_{e}\\}_{e\in E(\widehat{\mathcal{T}})}$-normal with
respect to $\widehat{B}$. Define a weighted incidence matrix ${B}$ of
${\mathcal{T}}$ by

$B(v,e)=\left\\{\begin{array}[]{ll}\widehat{B}(v,e),&\mbox{if\leavevmode\nobreak\
}v\in V(\widehat{T})\setminus\\{u\\},e\in E(\widehat{T})\mbox{\
and\leavevmode\nobreak\ }v\in e;\\\ 1-\sum\limits_{g\in
P_{\mathcal{T}}(u)}\alpha_{e},&\mbox{if\leavevmode\nobreak\ }v=u\mbox{\
and\leavevmode\nobreak\ }e=f;\\\ \alpha_{e},&\mbox{if\leavevmode\nobreak\
}v=u\mbox{\ and\leavevmode\nobreak\ }e\in P_{\mathcal{T}}(u);\\\
1,&\mbox{if\leavevmode\nobreak\ }v\neq u,v\in e\mbox{\ and\leavevmode\nobreak\
}e\in P_{\mathcal{T}}(u);\\\ 0,&\mbox{if\leavevmode\nobreak\ }v\notin
e.\end{array}\right.$

Then one may check that $\mathcal{T}$ is generalized $\\{\alpha_{e}\\}_{e\in
E(\mathcal{T})}$-normal with respect to ${B}$, as desired. ∎

######  Remark 3.7.

Note that the converses of (1) and (2) in Lemma 3.6 also hold by their proof.
However, these facts are not needed in this paper.

######  Lemma 3.8.

Let $\mathcal{T}$ be a $k$-star and $\alpha_{e}\neq 0$ for any $e\in
E(\mathcal{T})$. If $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ is a root of
$\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in E(\mathcal{T})}\right)$,
then $\mathcal{T}$ is generalized $\\{\alpha_{e}\\}_{e\in
E(\mathcal{T})}$-normal.

###### Proof.

Clearly, $\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in
E(\mathcal{T})}\right)=1-\sum_{e\in E(\mathcal{T})}x_{e}$. If
$\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ is a root of
$\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in E(\mathcal{T})}\right)$,
then $\sum_{e\in E(\mathcal{T})}\alpha_{e}=1.$ Let $u\in V(\mathcal{T})$ such
that the degree of $u$ equals $\Delta(\mathcal{T})$. Define a weighted
incidence matrix ${B}$ of $\mathcal{T}$ by

$B(v,e)=\left\\{\begin{array}[]{ll}\alpha_{e},&\mbox{if\leavevmode\nobreak\
}v=u\mbox{\ and\leavevmode\nobreak\ }e\in E(\mathcal{T});\\\
1,&\mbox{if\leavevmode\nobreak\ }v\neq u,v\in e\mbox{\ and\leavevmode\nobreak\
}e\in E(\mathcal{T})\\\ 0,&\mbox{if\leavevmode\nobreak\ }v\notin
e.\end{array}\right.$

Then $\mathcal{T}$ is generalized $\\{\alpha_{e}\\}_{e\in
E(\mathcal{F})}$-normal with respect to ${B}$. The proof is completed. ∎

By Lemma 3.8, we immediately get the following result which will be used in
later.

######  Corollary 3.9.

Let $\mathcal{T}$ be a $k$-tree with $\Delta(\mathcal{T})\geq 2$ and
$\alpha_{e}\neq 0$ for any $e\in E(\mathcal{T})$. If
$(\mathcal{T},u,P_{\mathcal{T}}(u))$ is inadmissible for some
$u\in\mathcal{N}(\mathcal{T})$, then the $k$-star $\mathcal{F}$ induced by
$P_{\mathcal{T}}(u)$ is generalized $\\{\alpha_{e}\\}_{e\in
E(\mathcal{F})}$-normal.

The following result is the key in the proof of Theorem 1.3 which suggests
that if $\alpha$ is a root of $\mu(\mathcal{T},x)$, then there exists a
subtree $\mathcal{F}$ of $\mathcal{T}$ such that $\mathcal{F}$ is generalized
$\alpha$-normal.

######  Lemma 3.10.

Let $\mathcal{T}$ be a $k$-tree, and let $\alpha_{e}\neq 0$ for any $e\in
E(\mathcal{T})$. If $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ is a root of
$\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in E(\mathcal{T})}\right)$,
then there exists a subtree $\mathcal{F}$ of $\mathcal{T}$ such that
$\mathcal{F}$ is generalized $\\{\alpha_{e}\\}_{e\in E(\mathcal{F})}$-normal.

###### Proof.

If $\mathcal{T}$ contains only one edge, it follows from Lemma 3.8. Assume
that $\Delta(\mathcal{T})\geq 2$ and $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$
is a root of $\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in
E(\mathcal{T})}\right)$. Our sketchy strategy will be to construct a sequence
$(\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$ consisting of subtrees of
$\mathcal{T}$ by applying Lemma 3.6 (1) repeatedly. Then, based on
$\mathcal{T}_{s}$, we repeatedly apply Lemma 3.6 (2) to obtain the required
subtree $\mathcal{F}$ such that $\mathcal{F}$ is generalized
$\\{\alpha_{e}\\}_{e\in E(\mathcal{F})}$-normal. Firstly, we provide an
algorithm to construct $(\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$, see
Algorithm 1.

Input : A $k$-tree $\mathcal{T}$ and a sequence $\\{\alpha_{e}\\}_{e\in
E(\mathcal{T})}$ with $\alpha_{e}\neq 0$ for any $e\in E(\mathcal{T})$.

Output : A sequence of subtrees $(\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$
with $\left(\\{\alpha^{1}_{e}\\}_{e\in
E({\mathcal{T}_{1}})},\ldots,\\{\alpha^{s}_{e}\\}_{e\in
E({\mathcal{T}_{s}})}\right)$.

1

2$i=1$, set $\mathcal{T}_{1}=\mathcal{T}$ and $\\{\alpha^{1}_{e}\\}_{e\in
E(\mathcal{T})}=\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$;

3 repeat

4 while  _$\big{(}\mathcal{T}_{i},\\{\alpha^{i}_{e}\\}_{e\in
E({\mathcal{T}_{i}})}\big{)}$ with $i\geq 1$_ do

5 if  _$\mathcal{N}(\mathcal{T}_{i})=\emptyset$ ,_ then

6 set $s=i$, stop and output $(\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$ with
$\left(\\{\alpha^{1}_{e}\\}_{e\in
E({\mathcal{T}_{1}})},\ldots,\\{\alpha^{s}_{e}\\}_{e\in
E({\mathcal{T}_{s}})}\right)$;

7

8 else

9 if  _there exists a vertex $u_{i}$ in $\mathcal{N}(\mathcal{T}_{i})$ such
that $(\mathcal{T}_{i},u_{i},P_{\mathcal{T}_{i}}(u_{i}))$ is inadmissible with
respect to $\\{\alpha^{i}_{e}\\}_{e\in E(\mathcal{T}_{i})}$,_ then

10 set $s=i$, stop and output $(\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$ with
$\left(\\{\alpha^{1}_{e}\\}_{e\in
E({\mathcal{T}_{1}})},\ldots,\\{\alpha^{s}_{e}\\}_{e\in
E({\mathcal{T}_{s}})}\right)$;

11

12 else

13 for any $u\in\mathcal{N}(\mathcal{T}_{i})$,
$(\mathcal{T}_{i},u,P_{\mathcal{T}_{i}}(u))$ is admissible with respect to
$\\{\alpha^{i}_{e}\\}_{e\in E(\mathcal{T}_{i})}$;

14 choose one vertex $u_{i}$ in $\mathcal{N}(\mathcal{T}_{i})$;

15 set $\mathbf{c}_{i}=\sum_{g\in P_{\mathcal{T}_{i}}(u_{i})}\alpha^{i}_{g}$;

16 set $\mathcal{T}_{i+1}$ to be the $k$-tree obtained from $\mathcal{T}_{i}$
by deleting all edges in $P_{\mathcal{T}_{i}}(u_{i})$ and the resultant
isolated vertices, where $P_{\mathcal{T}_{i}}(u_{i})$ is the set consisting of
$d_{\mathcal{T}_{i}}(u_{i})-1$ chosen pendent edges incident to $u_{i}$ in
$\mathcal{T}_{i}$;

17 define $\\{\alpha^{i+1}_{e}\\}_{e\in E(\mathcal{T}_{i+1})}$ as follows. Set
$\alpha^{i+1}_{f_{i}}=\frac{\alpha^{i}_{f_{i}}}{1-\mathbf{c}_{i}},$ and
$\alpha^{i+1}_{e}=\alpha^{i}_{e}$ for any $e\in
E(\mathcal{T}_{i+1}\\})\setminus\\{f_{i}\\}$, where $f_{i}$ is the only edge
incident to $u_{i}$ in $\mathcal{T}_{i}$ but none of
$P_{\mathcal{T}_{i}}(u_{i})$;

18 replace $i$ by $i+1$ and return
$(\mathcal{T}_{i},\\{\alpha^{i}_{e}\\}_{e\in E({\mathcal{T}_{i}})})$;
$\triangleright$ repeat for $i$

19 end if

20

21 end if

22

23 end while

24

25until  _output $(\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$ with
$\left(\\{\alpha^{1}_{e}\\}_{e\in
E({\mathcal{T}_{1}})},\ldots,\\{\alpha^{s}_{e}\\}_{e\in
E({\mathcal{T}_{s}})}\right)$_;

Algorithm 1 A search for $(\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$

We are now ready to obtain the required subtree $\mathcal{F}$ such that
$\mathcal{F}$ is generalized $\\{\alpha_{e}\\}_{e\in E(\mathcal{F})}$-normal.
Note that the algotithm will stop when
$\mathcal{N}(\mathcal{T}_{s})=\emptyset$ or
$(\mathcal{T}_{s},u_{s},P_{\mathcal{T}_{s}}(u_{s}))$ is inadmissible with
respect to $\\{\alpha^{s}_{e}\\}_{e\in E(\mathcal{T})}$. Based on this, we
divide the remaining proof into two cases.

Case 1: $\mathcal{N}(\mathcal{T}_{s})=\emptyset$. This implies that
$\mathcal{T}_{s}$ contains only one edge. In this case, we will show that
$\mathcal{F}=\mathcal{T}$. Consider the sequence
$(\mathcal{T}=\mathcal{T}_{1},\ldots,\mathcal{T}_{s})$. It follows from Step
10 of Algorithm 1 that $(\mathcal{T}_{i},u_{i},P_{\mathcal{T}_{i}}(u_{i}))$ is
admissible with respect to $\\{\alpha^{i}_{e}\\}_{e\in E({\mathcal{T}_{i}})}$
for any $1\leq i\leq s-1$. Note that $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$
is a root of $\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in
E(\mathcal{T})}\right)$. Thus, we can conclude that
$\\{\alpha^{i}_{e}\\}_{e\in E({\mathcal{T}_{i}})}$ is a root of
$\widetilde{\mu}\left({\mathcal{T}_{i}},\\{x_{e}\\}_{e\in
E({\mathcal{T}_{i}})}\right)$ for $2\leq i\leq s$ by applying repeatedly Lemma
3.6 (1). Since $\mathcal{T}_{s}$ contains only one edge, by Lemma 3.8,
$\mathcal{T}_{s}$ is generalized $\\{\alpha^{s}_{e}\\}_{e\in
E({\mathcal{T}_{s}})}$-normal. Applying Lemma 3.6 (2) repeatedly to
$\mathcal{T}_{i}$ for each $i$ from $2$ to $s$, we conclude that
$\mathcal{T}_{i}$ is generalized $\\{\alpha^{i}_{e}\\}_{e\in
E({\mathcal{T}_{i}})}$-normal for $1\leq i\leq s-1$. The assertion follows if
we take $\mathcal{F}=\mathcal{T}_{1}$.

Case 2: $(\mathcal{T}_{s},u_{s},P_{\mathcal{T}_{s}}(u_{s}))$ is inadmissible
with respect to $\\{\alpha^{s}_{e}\\}_{e\in E(\mathcal{T})}$. Similarly, we
can conclude that $\\{\alpha^{i}_{e}\\}_{e\in E({\mathcal{T}_{i}})}$ is a root
of $\widetilde{\mu}\left({\mathcal{T}_{i}},\\{x_{e}\\}_{e\in
E({\mathcal{T}_{i}})}\right)$ for $2\leq i\leq s$. Since
$(\mathcal{T}_{s},u_{s},P_{\mathcal{T}_{s}}(u_{s}))$ is inadmissible with
respect to $\\{\alpha^{s}_{e}\\}_{e\in E(\mathcal{T})}$, it follows from
Corollary 3.9 that the $k$-star $\widehat{\mathcal{F}}$ induced by the edge
set $P_{\mathcal{T}_{s}}(u_{s})$ is generalized $\\{\alpha^{s}_{e}\\}_{e\in
E(\widehat{\mathcal{F}})}$-normal.

Let $\mathcal{F}^{\prime}$ be the subforest of $\mathcal{T}$ induced by
$\cup_{i=1}^{s}P_{\mathcal{T}_{i}}(u_{i})$, and let $\mathcal{F}$ be the
component of $\mathcal{F}^{\prime}$ containing $P_{\mathcal{T}_{s}}(u_{s})$.
Next, we will show that $\mathcal{F}$ is exactly a desired subtree. Clearly,
there exists a sequence of natural numbers $1<a_{1}<a_{2}<\cdots<a_{\ell}=s$
such that

$E(\mathcal{F})=\cup_{i=1}^{\ell}P_{\mathcal{T}_{a_{i}}}(u_{a_{i}}).$

Denote by $\mathcal{F}_{a_{i}}$ the subforest of $\mathcal{T}$ induced by edge
set $\cup_{j=i}^{\ell}P_{\mathcal{T}_{a_{i}}}(u_{a_{i}})$ for any $1\leq
i\leq\ell$. We can get a sequence of $k$-trees as follows

$(\mathcal{F}=\mathcal{F}_{a_{1}},\mathcal{F}_{a_{2}},\ldots,\mathcal{F}_{a_{\ell-1}},\mathcal{F}_{a_{\ell}}=\widehat{\mathcal{F}}).$

Indeed, $\mathcal{F}_{a_{i}}$ can be obtained from $\mathcal{F}_{a_{i-1}}$ by
deleting all edges in $P_{\mathcal{T}_{a_{i-1}}}(u_{a_{i-1}})$ and the
resultant isolated vertices for any $2\leq i\leq\ell$.

As mentioned above, $\mathcal{F}_{a_{\ell}}$ is generalized
$\\{\alpha^{a_{\ell}}_{e}\\}_{e\in E(\mathcal{F}_{a_{\ell}})}$-normal. If
$a_{\ell}-1=a_{\ell-1}$, by Lemma 3.6 (2), it is clear that
$\mathcal{F}_{a_{\ell-1}}$ is generalized $\\{\alpha^{a_{\ell-1}}_{e}\\}_{e\in
E(\mathcal{F}_{a_{\ell-1}})}$-normal. If not, we write the continuous natural
numbers between $a_{\ell-1}$ and $a_{\ell}$ as

$a_{\ell-1}<a_{\ell-1}+1<\ldots<a_{\ell}-1<a_{\ell}.$

Recall that Step 14 of Algorithm 1 suggests that for any $1\leq i\leq s-1$,
$\alpha^{i}_{e}=\alpha^{i+1}_{e}$ for any $e\in E(\mathcal{T}_{i+1})$ unless
$e=f_{i}$, as well as the subgraph of $\mathcal{T}$ induced by $f_{i}\cup
P_{\mathcal{T}_{i}}(u_{i})$ is a $k$-star. Note that $E(\mathcal{F})$ and
$\cup_{a_{\ell-1}+1}^{a_{\ell}-1}P_{\mathcal{T}_{a_{i}}}(u_{a_{i}})$ are
disjoint. Thus,

$\alpha^{a_{\ell-1}+1}_{e}=\cdots=\alpha^{a_{\ell}-1}_{e}=\alpha^{a_{\ell}}_{e}$

for any $e\in E(\mathcal{F}_{a_{\ell}})$. Therefore, $\mathcal{F}_{a_{\ell}}$
is generalized $\\{\alpha^{a_{\ell-1}+1}_{e}\\}_{e\in
E(\mathcal{F}_{a_{\ell}})}$-normal. It follows from Lemma 3.6 (2) that
$\mathcal{F}_{a_{\ell-1}}$ is generalized $\\{\alpha^{a_{\ell-1}}_{e}\\}_{e\in
E(\mathcal{F}_{a_{\ell-1}})}$-normal. Repeating the above discussion to
$\mathcal{F}_{a_{i}}$ for each $i$ from $\ell-1$ to $2$, we have that
$\mathcal{F}_{a_{1}}$ is generalized $\\{\alpha^{a_{1}}_{e}\\}_{e\in
E(\mathcal{F}_{a_{1}})}$-normal.

To finish the proof, it suffices to prove

(3.6) $\alpha^{a_{1}}_{e}=\alpha_{e}{\rm\leavevmode\nobreak\
for\leavevmode\nobreak\ any\leavevmode\nobreak\ }e\in E(\mathcal{F}_{a_{1}}).$

It is obvious for $a_{1}=1$. If $a_{1}\neq 1$, then for any $2\leq j\leq
a_{1}$, by the algorithm, we have

(3.7) $\alpha^{j}_{e}=\alpha^{j-1}_{e}{\rm\leavevmode\nobreak\
for\leavevmode\nobreak\ any\leavevmode\nobreak\ }e\in
E(\mathcal{T}_{j})\setminus\\{f_{j-1}\\}.$

Since $E(\mathcal{F}_{a_{1}})\subseteq E(\mathcal{T}_{a_{1}})$, and
$f_{j}\notin E(\mathcal{F}_{a_{1}})$ for any $1\leq j\leq a_{1}-1$, we
conclude (3.6) from (3.7). This completes the proof.

∎

######  Lemma 3.11.

Let $\mathcal{T}$ be a $k$-tree with $k\geq 3$. Then $0$ is an eigenvalue of
$\mathcal{A}(\mathcal{T})$.

###### Proof.

Fix a vertex $u\in V(\mathcal{T})$. Let
$\mathbf{u}\in\mathbb{R}^{|V(\mathcal{T})|}$ be the vector whose $u$-th entry
is $1$ and other entries are $0$. By the assumption ‘$k\geq 3$’, one may check
that the vector $\mathbf{u}$ is a eigenvector of $\mathcal{A}(\mathcal{T})$
associated with the eigenvalue $0$, as desired. ∎

######  Theorem 3.12.

Let $\mathcal{T}$ be a $k$-tree with the matching polynomial
$\mu(\mathcal{T},x)$. Then every zero of $\mu(\mathcal{T},x)$ is an eigenvalue
of the adjacency tensor of $\mathcal{T}$.

###### Proof.

If $k=2$, then the result follows from Theorem 1.1. Assume that $k\geq 3$. By
Lemma 3.11, $0$ is an eigenvalue of $\mathcal{A}(\mathcal{T})$. Let
$\lambda\neq 0$ be a root of $\mu(\mathcal{T},x)$. Then

$\mu(\mathcal{T},\lambda)=\lambda^{|V(\mathcal{T})|}\sum_{r\geq
0}(-1)^{r}p(\mathcal{T},r)\left(\lambda^{-k}\right)^{r}=0.$

Thus, $\\{\lambda^{-k}\\}_{e\in E(\mathcal{T})}$ is a root of
$\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in E(\mathcal{T})}\right)$.
By Lemma 3.10, there exists a subtree $\mathcal{F}$ of $\mathcal{T}$ such that
$\mathcal{F}$ is generalized $\lambda^{-k}$-normal. Hence $\lambda$ is an
eigenvalue of $\mathcal{A}(\mathcal{F})$ by Lemma 3.5. Moreover, by Corollary
3.3, $\lambda$ is an eigenvalue of $\mathcal{A}({\mathcal{T}})$. Therefore,
every nonzero root of $\mu(\mathcal{T},x)$ is an eigenvalue of
$\mathcal{A}({\mathcal{T}})$. This completes the proof. ∎

We are now ready to prove Theorem 1.3.

###### Proof of Theorem 1.3..

Note that the first statement of Theorem 1.3 is exactly Theorem 3.12. Thus we
only need to prove that $\lambda(\mathcal{T})$ is a root of
$\mu(\mathcal{T},x)$ and equals to the spectral radius of the adjacency tensor
of $\mathcal{T}$.

If $\lambda$ is a zero of $\mu(\mathcal{T},x)$, then $\lambda$ is an
eigenvalue of $\mathcal{A}(\mathcal{T})$ by Theorem 3.12. Thus
$|\lambda|\leq\rho(\mathcal{T})$ by the definition of spectral radius. Hence
we have $\lambda(\mathcal{T})\leq\rho(\mathcal{T})$. We next prove that
$\rho(\mathcal{T})$ is a root of $\mu(\mathcal{T},x)$.

By Lemma 3.1, $\rho(\mathcal{T})$ is an eigenvalue of
$\mathcal{A}(\mathcal{T})$ with an corresponding eigenvector having all
elements positive. Applying this fact to Lemma 3.5, we obtain that
$\mathcal{H}$ is generalized $\alpha$-normal with
$\alpha=\rho(\mathcal{T})^{-k}$. Moreover, [50, Lemma 3.1] suggests that if
$\mathcal{T}$ is generalized $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$-normal,
then $\\{\alpha_{e}\\}_{e\in E(\mathcal{T})}$ is a root of
$\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in E(\mathcal{T})}\right)$.
We conclude that $\\{\rho(\mathcal{T})^{-k}\\}_{e\in E(\mathcal{T})}$ is a
root of the polynomial

$\widetilde{\mu}\left(\mathcal{T},\\{x_{e}\\}_{e\in
E(\mathcal{T})}\right)=\sum_{M\in\mathcal{M}(\mathcal{T})}(-1)^{|M|}\prod_{e\in
E(M)}x_{e}.$

This implies that $\rho(\mathcal{T})$ is a root of the polynomial

$x^{|V(\mathcal{T})|}\sum_{M\in\mathcal{M}(\mathcal{T})}(-1)^{|M|}x^{-k|M|}=\mu(\mathcal{T},x),$

as desired. This completes the proof. ∎

##  4\. The distribution of zeros of the matching polynomial

This section is devoted to studying the distribution of zeros of the matching
polynomial. We mainly prove that every zero of $\mu(\mathcal{H},x)$ is an
eigenvalue of the adjacency tensor of $\mathcal{T}(\mathcal{H},u)$ and the
cyclic index of $\mu(\mathcal{H},x)$ is exactly equal to $k$. Furthermore, we
show that $\lambda(\mathcal{H})$, the maximum modulus of all zeros of
$\mu(\mathcal{H},x)$ is a simple root of $\mu(\mathcal{H},x)$ and is exactly
the spectral radius of the adjacency tensor of $\mathcal{T}(\mathcal{H},u)$.
Using these facts, we provide the lower and upper bounds of
$\lambda(\mathcal{H})$ and complete the proof of Theorem 1.4.

###  4.1. Zeros of the matching polynomials of $k$-graphs

Theorems 1.1 and 2.8 establish a bridge between the zeros of the matching
polynomial of $\mathcal{H}$ and the eigenvalues of the path tree
$\mathcal{T}(\mathcal{H},u)$. Next, we will prove that every zero of
$\mu(\mathcal{H},x)$ is an eigenvalue of the adjacency tensor of
$\mathcal{T}(\mathcal{H},u)$ and the cyclic index of $\mu(\mathcal{H},x)$ is
equal to $k$.

######  Lemma 4.1 ([45]).

Let $\mathcal{H}$ be a $k$-graph. Then,

$\frac{d}{dx}\mu(\mathcal{H},x)=\sum_{v\in
V(\mathcal{H})}\mu(\mathcal{H}-v,x).$

######  Theorem 4.2.

Let $\mathcal{H}$ be a connected $k$-graph and $u\in V(\mathcal{H})$. Then
every zero of $\mu(\mathcal{H},x)$ is an eigenvalue of
$\mathcal{A}(\mathcal{T}(\mathcal{H},u))$. Moreover, $\lambda(\mathcal{H})$ is
a simple root of $\mu(\mathcal{H},x)$ and equals to
$\rho(\mathcal{T}(\mathcal{H},u))$.

###### Proof.

By Theorem 2.8, $\mu(\mathcal{H},x)$ divides
$\mu(\mathcal{T}(\mathcal{H},u),x)$, so every zero of $\mu(\mathcal{H},x)$ is
a zero of $\mu(\mathcal{T}(\mathcal{H},u),x)$. By Lemma 2.4 (1),
$\mathcal{T}(\mathcal{H},u)$ is a tree. Thus every zero of
$\mu(\mathcal{T}(\mathcal{H},u),x)$ is an eigenvalue of
$\mathcal{A}(\mathcal{T}(\mathcal{H},u))$ by Theorem 1.3. We therefore deduce
that every zero of $\mu(\mathcal{H},x)$ is an eigenvalue of
$\mathcal{A}(\mathcal{T}(\mathcal{H},u))$. This proves the first statement.

We next prove that $\lambda(\mathcal{H})$ is a root of $\mu(\mathcal{H},x)$
and equals to $\rho(\mathcal{T}(\mathcal{H},u))$. By Theorem 2.8, there exists
a proper subforest $\mathcal{F}$ of $\mathcal{T}(\mathcal{H},u)$ such that

(4.1)
$\displaystyle\mu(\mathcal{H},x)\mu(\mathcal{F},x)=\mu(\mathcal{T}(\mathcal{H},u),x),$

which implies that
$\lambda(\mathcal{T}(\mathcal{H},u))=\max\\{\lambda(\mathcal{H}),\lambda(\mathcal{F})\\}$.
By Lemma 3.1, we have $\rho(\mathcal{F})<\rho(\mathcal{T}(\mathcal{H},u))$.
Besides, by Theorem 1.3, we have $\lambda(\mathcal{F})=\rho(\mathcal{F})$ and
$\lambda(\mathcal{T}(\mathcal{H},u))=\rho(\mathcal{T}(\mathcal{H},u))$. Thus
$\lambda(F)<\lambda(\mathcal{T}(\mathcal{H},u))$. We conclude that

(4.2)
$\displaystyle\lambda(\mathcal{H})=\lambda(\mathcal{T}(\mathcal{H},u))=\rho(\mathcal{T}(\mathcal{H},u)).$

It remains to prove that $\lambda(\mathcal{H})$ is a simple root of
$\mu(\mathcal{H},x)$. For every $v\in V(\mathcal{H})$, we claim
$\lambda(\mathcal{H})>\lambda(\mathcal{H}-v)$. Let
$\mathcal{H}_{1},\ldots,\mathcal{H}_{s}$ be the components of $\mathcal{H}-v$.
Without loss of generality, one may assume

(4.3) $\displaystyle\lambda(\mathcal{H}_{1})=\max_{1\leq i\leq
s}\lambda(\mathcal{H}_{i}).$

By (2.1), we have $\lambda(\mathcal{H}-v)=\lambda(\mathcal{H}_{1})$. By (4.2),
we further have $\lambda(\mathcal{H})=\rho(\mathcal{T}(\mathcal{H},v))$ and
$\lambda(\mathcal{H}-v)=\lambda(\mathcal{H}_{1})=\rho(\mathcal{T}(\mathcal{H}_{1},v_{1}))$,
where $v_{1}$ is a vertex of $V(\mathcal{H}_{1})$ such that $v_{1}\in
N_{\mathcal{H}}(v)$. Observe that $\mathcal{T}(\mathcal{H}_{1},v_{1})$ is a
proper subtree of $\mathcal{T}(\mathcal{H},v)$. Thus
$\rho(\mathcal{T}(\mathcal{H},v))>\rho(\mathcal{T}(\mathcal{H}_{1},v))$ by
Lemma 3.1. This implies $\lambda(\mathcal{H})>\lambda(\mathcal{H}-v)$, as
desired.

Note that the leading coefficient of $\sum_{v\in
V(\mathcal{H})}\mu(\mathcal{H}-v,x)$ is positive. It follows from above claim
that $\sum_{v\in V(\mathcal{H})}\mu(\mathcal{H}-v,x)$ is positive whenever
$x\geq\lambda(\mathcal{H})$. Therefore, $\lambda(\mathcal{H})$ is not a root
of $\frac{d}{dx}\mu(\mathcal{H},x)$ by Lemma 4.1, and hence the root
$\lambda(\mathcal{H})$ of $\mu(\mathcal{H},x)$ is simple. This completes the
proof of the theorem. ∎

As an application of Theorem 4.2, we have the following theorem.

######  Theorem 4.3.

Let $\mathcal{H}$ be a connected $k$-graph. Then the cyclic index of
$\mu(\mathcal{H},x)$ is equal to $k$.

###### Proof.

For the $k$-th root of unity $\xi$, one can check the following equalities:

$\mu(\mathcal{H},\xi x)=\sum_{r\geq 0}(-1)^{r}p(\mathcal{H},r)(\xi
x)^{|V(\mathcal{H})|-kr}=\xi^{|V(\mathcal{H})|}\mu(\mathcal{H},x).$

This implies that $\mu(\mathcal{H},x)$ is $k$-symmetric, so $k\leq c$, where
$c$ is the cyclic index of $\mu(\mathcal{H},x)$.

Since $\mu(\mathcal{H},x)$ is $c$-symmetric and $\lambda(\mathcal{H})$ is a
simple root of $\mu(\mathcal{H},x)$, we have that
$\lambda(\mathcal{H})e^{\mathbf{i}\frac{2\pi j}{c}},j=0,1,\ldots,c-1$ are
zeros of $\mu(\mathcal{H},x)$. By Theorem 4.2, they are eigenvalues of a path
tree $\mathcal{T}(\mathcal{H},u)$ of $\mathcal{H}$ with modulus
$\rho(\mathcal{T}(\mathcal{H},u))$. Let $d$ be the cyclic index of the
characteristic polynomial of $\mathcal{A}(\mathcal{T}(\mathcal{H},u))$. By
Theorem 2.6 and Eq. (2.7) in [9] , $\mathcal{T}(\mathcal{H},u)$ has exactly
$d$ distinct eigenvalues with modulus $\rho(\mathcal{T}(\mathcal{H},u))$.
Thus, $d\geq c$. Furthermore, [9, Corollary 4.3] states that $d|k$ for any
$k$-graph. Therefore, $d=k=c$, that is, the cyclic index of
$\mu(\mathcal{H},x)$ is exactly $k$. ∎

######  Remark 4.4.

From the proof of Theorem 4.3, we also get that $\mu(\mathcal{H},x)$ has
exactly $k$ distinct zeros with modulus $\lambda(\mathcal{H})$ and they are
equally distributed on complex plane, equivalently, they are
$\lambda(\mathcal{H})e^{\frac{2\pi j}{k}\mathbf{i}},j=0,1,\ldots,k-1.$ We
therefore conclude that $\mu(\mathcal{H},x)$ is $\ell$-symmetric if and only
if $\ell$ divides $k$.

###  4.2. The largest zero of the matching polynomial

In this subsection, we present lower and upper bounds for
$\lambda(\mathcal{H})$ and complete the proof of Theorem 1.4.

######  Lemma 4.5.

Let $\mathcal{H}$ be a connected $k$-graph. For any subgraph $\mathcal{G}$ of
$\mathcal{H}$, we have $\lambda(\mathcal{G})\leq\lambda(\mathcal{H})$ with
equality holds if and only if $\mathcal{G}=\mathcal{H}$.

###### Proof.

Without loss of generality, we may assume that $\mathcal{G}$ is connected.
Otherwise, we can get the result by considering each components of
$\mathcal{G}$. Let $u$ be a vertex of $\mathcal{G}$. Since $\mathcal{G}$ is a
subgraph of $\mathcal{H}$ containing $u$, $\mathcal{T}(\mathcal{G},u)$ is a
subgraph $\mathcal{T}(\mathcal{H},u)$. By Theorem 4.2 and Lemma 3.1, we have

$\lambda(\mathcal{G})=\rho(\mathcal{T}(\mathcal{G},u))\leq\rho(\mathcal{T}(\mathcal{H},u))=\lambda(\mathcal{H})$

with equality holds if and only if
$\mathcal{T}(\mathcal{G},u)=\mathcal{T}(\mathcal{H},u)$. Obverse that
$\mathcal{T}(\mathcal{G},u)=\mathcal{T}(\mathcal{H},u)$ if and only if
$\mathcal{G}=\mathcal{H}$. The result follows. ∎

######  Corollary 4.6.

Let $\mathcal{H}$ be a connected $k$-graph with maximum degree ${\Delta}$.
Then $\lambda(\mathcal{H})\geq\Delta^{1\over k}$ with equality if and only if
all edges of $\mathcal{H}$ share a common vertex.

###### Proof.

Let $\mathcal{S}_{\Delta}$ be the $k$-star with maximum degree ${\Delta}$,
that is, a graph consisting of ${\Delta}$ edges sharing a common vertex.
Clearly,

$\mu(\mathcal{S}_{\Delta},x)=x^{\Delta k-\Delta-k+1}(x^{k}-\Delta),$

and thus $\lambda(\mathcal{S}_{\Delta})=\Delta^{1\over k}$.

Let $u$ be a vertex of $\mathcal{H}$ with $d_{\mathcal{H}}(u)=\Delta$. Then,
$\mathcal{T}(\mathcal{H},u)$ contains $\mathcal{S}_{\Delta}$ as a subgraph. By
(4.2) and Lemma 4.5, we have

$\lambda(\mathcal{H})=\lambda(\mathcal{T}(\mathcal{H},u))\geq\lambda(\mathcal{S}_{\Delta})=\Delta^{1\over
k}$

with equality holds if and only if
$\mathcal{T}(\mathcal{H},u)=\mathcal{S}_{\Delta}.$ If all edges of
$\mathcal{H}$ have a common vertex $u$, then
$\mathcal{T}(\mathcal{H},u)=\mathcal{S}_{\Delta}$ by the definition of path
trees. Conversely, if $\mathcal{T}(\mathcal{H},u)=\mathcal{S}_{\Delta}$, then
$\mathcal{H}$ has exactly $\Delta$ edges as
$|E(\mathcal{H})|\leq|E(\mathcal{T}(\mathcal{H},u))|=\Delta$ and
$\Delta(\mathcal{H})=\Delta$, which implies that all edges of $\mathcal{H}$
have a common vertex. ∎

######  Lemma 4.7.

Let $\mathcal{H}$ be a connected $k$-graph with maximum degree $\Delta$ and
$u$ be a vertex. For any integer $\xi\geq\max\\{\Delta,2\\}$, if
$d_{\mathcal{H}}(u)<\xi$, then the inequality

$\displaystyle\frac{\mu(\mathcal{H},x)}{\mu(\mathcal{H}-u,x)}>{\big{(}(k-1)(\xi-1)\big{)}^{1\over
k}}$

holds for $x\geq\frac{k}{k-1}\big{(}(k-1)(\xi-1)\big{)}^{1\over k}$.

###### Proof.

We prove the statement by induction on $n=|V(\mathcal{H})|$. If $n=k$, then
$\mathcal{H}$ is the graph consisting of a single edge and thus one may verify
that

$\displaystyle\frac{\mu(\mathcal{H},x)}{\mu(\mathcal{H}-u,x)}=\frac{x^{k}-1}{x^{k-1}}=x-\frac{1}{x^{k-1}}>$
$\displaystyle\big{(}(k-1)(\xi-1)\big{)}^{1\over k}$

holds for $x\geq\frac{k}{k-1}\big{(}(k-1)(\xi-1)\big{)}^{1\over k}$, since

$\displaystyle x-\frac{1}{x^{k-1}}\geq$
$\displaystyle\frac{k}{k-1}\big{(}(k-1)(\xi-1)\big{)}^{1\over
k}-\frac{1}{\frac{k^{k-1}}{(k-1)^{k-1}}\big{(}(k-1)(\xi-1)\big{)}^{k-1\over
k}}$ $\displaystyle=$ $\displaystyle\big{(}(k-1)(\xi-1)\big{)}^{1\over
k}\left(1+\frac{1}{k-1}\left(1-\frac{(k-1)^{k-1}}{(\xi-1)k^{k-1}}\right)\right)$
$\displaystyle>$ $\displaystyle\big{(}(k-1)(\xi-1)\big{)}^{1\over k}.$

We now assume that $n\geq k+1$. It follows from the connectedness of
$\mathcal{H}$ that $\Delta\geq 2$, and thus $\Delta\leq\xi$. For any edge
$e=\\{u,v_{2},\ldots,v_{k}\\}\in E_{\mathcal{H}}(u)$, let
$V_{i}(e)=\\{u,v_{2},\ldots,v_{i}\\}$ for each $i\geq 2$ and
$V_{1}(e)=\\{u\\}$. Note that for any $i\in[n-1]$, we have that
$\Delta(\mathcal{H}-V_{i}(e))\leq\Delta$ and
$d_{\mathcal{H}-V_{i}}(v_{i+1})<\Delta$. By induction hypothesis and (2.2), we
derive that for any $i\in[n-1]$,

$\frac{\mu(\mathcal{H}-V_{i+1}(e),x)}{\mu(\mathcal{H}-V_{i}(e),x)}\leq\frac{1}{\big{(}(k-1)(\xi-1)\big{)}^{1\over
k}}$

holds for $x\geq\frac{k}{k-1}\big{(}(k-1)(\xi-1)\big{)}^{1\over k}$. Thus for
any $e\in E_{\mathcal{H}}(u)$,

(4.4)
$\displaystyle\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}=\prod_{i=1}^{k-1}\frac{\mu(\mathcal{H}-V_{i+1}(e),x)}{\mu(\mathcal{H}-V_{i}(e),x)}\leq\frac{1}{\big{(}(k-1)(\xi-1)\big{)}^{k-1\over
k}}$

while $x\geq\frac{k}{k-1}\big{(}(k-1)(\xi-1)\big{)}^{1\over k}$.

By Lemma 2.6 and (4.4), combining the fact $d_{\mathcal{H}}(u)\leq\xi-1$, we
have that

(4.5) $\displaystyle\frac{\mu(\mathcal{H},x)}{\mu(\mathcal{H}-u,x)}=$
$\displaystyle x-\sum_{e\in
E_{\mathcal{H}}(u)}\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}$
$\displaystyle=$ $\displaystyle x-\sum_{e\in
E_{\mathcal{H}}(u)}\prod_{i=1}^{k-1}\frac{\mu(\mathcal{H}-V_{i+1}(e),x)}{\mu(\mathcal{H}-V_{i}(e),x)}$
$\displaystyle>$ $\displaystyle\frac{k}{k-1}\big{(}(k-1)(\xi-1)\big{)}^{1\over
k}-\frac{\xi-1}{{\big{(}(k-1)(\xi-1)\big{)}^{k-1\over k}}}$ $\displaystyle=$
$\displaystyle\big{(}(k-1)(\xi-1)\big{)}^{1\over k}$

holds for $x\geq\frac{k}{k-1}\big{(}(k-1)(\xi-1)\big{)}^{1\over k}$. This
completes the proof. ∎

######  Theorem 4.8.

Let $G$ be a connected $k$-graph with maximum degree ${\Delta}\geq 2$. Then

$\lambda(G)<\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}.$

###### Proof.

Let $\mathcal{H}$ be a $k$-graph with maximum degree ${\Delta}\geq 2$. By
Theorem 4.2, $\lambda(\mathcal{H})$ is the largest real zero of
$\mu(\mathcal{H},x)$, so it suffices to show that $\mu(\mathcal{H},x)>0$ for
$x\geq\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}$. We prove it by
induction on $n$. Let $u$ be a vertex of $\mathcal{H}$ with
$d_{\mathcal{H}}(u)=\delta(\mathcal{H})$. For $n=k+1$, it is clear that
$\mathcal{H}$ consists of two edges sharing $k-1$ vertices. Thus we have

$\mu(\mathcal{H}-u,x)=x^{k}-1>0$

when $x\geq\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}>1$. In
addition, by Lemma 2.6,

$\displaystyle\frac{\mu(\mathcal{H},x)}{\mu(\mathcal{H}-u,x)}=$ $\displaystyle
x-\sum_{e\in
E_{\mathcal{H}}(u)}\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}$
$\displaystyle=$ $\displaystyle x-\sum_{e\in
E_{\mathcal{H}}(u)}\frac{x}{x^{k}-1}$ $\displaystyle\geq$
$\displaystyle\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over
k}\left(1-\frac{\Delta}{\frac{k^{k}}{(k-1)^{k-1}}(\Delta-1)-1}\right)$
$\displaystyle=$
$\displaystyle\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over
k}\left(\frac{k^{k}(\Delta-1)-(k-1)^{k-1}(\Delta+1)}{k^{k}(\Delta-1)-(k-1)^{k-1}}\right)$
$\displaystyle>$ $\displaystyle 0$

for $x\geq\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}$. This implies
the statement for $n=k+1$.

Assume $n>k+1$. For any edge $e=\\{u,v_{2},\ldots,v_{k}\\}\in
E_{\mathcal{H}}(u)$, denote $V_{i}(e)=\\{u,v_{2},\ldots,v_{i}\\}$ for each
$i\geq 2$ and $V_{1}(e)=\\{u\\}$. By Lemma 4.7 and the fact
$d_{\mathcal{H}-V_{i}}(v_{i+1})<\Delta$, for any $i\in[n-1]$, the inequlity

$\frac{\mu(\mathcal{H}-V_{i+1}(e),x)}{\mu(\mathcal{H}-V_{i}(e),x)}\leq\frac{1}{\big{(}(k-1)(\Delta-1)\big{)}^{1\over
k}}$

holds for $x\geq\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}$. Thus,
for any edge $e\in E_{\mathcal{H}}(u)$,

(4.6)
$\displaystyle\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-u,x)}=\prod_{i=1}^{k-1}\frac{\mu(\mathcal{H}-V_{i+1}(e),x)}{\mu(\mathcal{H}-V_{i}(e),x)}\leq\frac{1}{\big{(}(k-1)(\Delta-1)\big{)}^{k-1\over
k}}$

when $x\geq\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}$. By Lemma
2.6 and (4.6),

$\displaystyle\frac{\mu(\mathcal{H},x)}{\mu(\mathcal{H}-v,x)}$
$\displaystyle=$ $\displaystyle\frac{x\mu(\mathcal{H}-v,x)-\sum_{e\in
E_{\mathcal{H}}(v)}\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-v,x)}$
$\displaystyle=$ $\displaystyle x-\sum_{e\in
E_{\mathcal{H}}(v)}\frac{\mu(\mathcal{H}-e,x)}{\mu(\mathcal{H}-v,x)}$
$\displaystyle>$
$\displaystyle\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over
k}-\frac{\Delta}{\big{(}(k-1)(\Delta-1)\big{)}^{k-1\over k}}$ $\displaystyle=$
$\displaystyle\frac{k(\Delta-1)-\Delta}{\big{(}(k-1)(\Delta-1)\big{)}^{k-1\over
k}}$ $\displaystyle\geq$ $\displaystyle 0$

when $x\geq\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}$. Note that
$\mu(\mathcal{H}-v,x)\neq 0$ for any
$x\geq\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}$ by induction
hypothesis. The result follows. ∎

We now have all the tools to prove Theorem 1.4.

###### Proof of Theorem 1.4..

Let $\mathcal{H}$ be a connected $k$-graph with maximum degree ${\Delta}\geq
2$. By Theorem 4.3, the cyclic index of $\mu(\mathcal{H},x)$ is $k$, and by
Theorem 4.2, $\lambda(\mathcal{H})$ is a simple root of $\mu(\mathcal{H},x)$.
Finally, the inequality (1.3) follows from Corollary 4.6 and Theorem 4.8. Thus
the proof is completed. ∎

##  5\. Concluding Remarks

In this paper, we present a fundamental characterization of the distribution
of zeros of the matching polynomials of $k$-graphs and generalize some results
on the classical matching polynomial to $k$-graphs. Note that most of the
results in this paper can be generalized to the multivariate weighted
$k$-graphs, a $k$-graph $\mathcal{H}=(V,E)$ associated with an edge-weighted
function $\mathbf{w}:E\rightarrow\mathbb{C}$ and a vertex-indeterminate
$\mathbf{x}=\\{x_{v}\\}_{v\in V}$, with some appropriate adjustment. For the
sake of simplicity, we chose not to pursue that direction in detail.

There is another interesting function related to the matching polynomial, the
matching generating function of a $k$-graph $\mathcal{H}$, which is defined by

$m(\mathcal{H},x)=\sum_{r\geq 0}p(\mathcal{H},r)x^{r}.$

Note that

$\mu(\mathcal{H},x)=\sum_{r\geq
0}(-1)^{r}p(\mathcal{H},r)x^{|V(\mathcal{H})|-kr}=x^{|V(\mathcal{H})|}\sum_{r\geq
0}p(\mathcal{H},r)(-x^{-k})^{r}$

Thus we have

(5.1)
$\displaystyle\mu(\mathcal{H},x)=x^{|V(\mathcal{H})|}m(\mathcal{H},-x^{-k}).$

Therefore, we can obtain some results similar to Theorem 2.7 and Theorem 2.8
for the matching generating functions.

As mentioned in Section 1, the result of Li and Mohar [31] indicates that for
a connected $k$-graph $\mathcal{H}$ with maximum degree $\Delta$, the
threshold bound

$\frac{k}{k-1}\big{(}(k-1)(\Delta-1)\big{)}^{1\over k}$

plays an important role in studying the second eigenvalue of $\mathcal{H}$.
Besides, Theorem 1.5 states that this value is exactly an upper bound of the
spectral radius of a connected $k$-tree with maximum degree $\Delta\geq 2$. In
fact, by combining Theorem 4.2 and Theorem 1.5, we may obtain another proof
for Theorem 1.4. Therefore, in the current setting, Theorem 1.4 can be viewed
as a new version of Theorem 1.5 from the view point of matching polynomials.
The main idea of [39] seems to imply that the former is more essential than
the latter in the study of the second eigenvalues of hypergraphs and Ramanujan
hypergraphs.

A sequence $a_{0},a_{1},\cdots,a_{n}$, of real numbers is said to be
logarithmically concave (or log-concave for short) if $a_{i}^{2}\geq
a_{i-1}a_{i+1}$ for all $1\leq i\leq n-1$. Many important sequences in
combinatorics are known to be log-concave. We refer the reader to a survey by
Stanley [44] for various examples and more background. Appling the rooted-
rootedness of the matching polynomial in Theorem 1.2, Heilmann and Lieb [24]
prove that the matching number sequence $\\{p(G,r)\\}_{r\geq 0}$ of a graph
$G$ is log-concave. However, for $k\geq 3$, the rooted-rootedness for matching
polynomials of $k$-graphs is invalid as proved in Theorem 1.4. Thus, it would
be interesting to study the log-concave property of the matching number
sequence of a $k$-graph.

## References

  * [1] J. Aihara, A new definition of Dewar-type resonance energy, J. Amer. Chem. Soc. 98 (1976), 2750–2758.
  * [2] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83–96.
  * [3] S. Bai and L. Lu, A bound on the spectral radius of hypergraphs with $e$ edges, Linear Algebra Appl. 549 (2018), 203–218.
  * [4] R. Chauvin, C. Lepetit, P. W. Fowler, and J. P. Malrieu, The chemical roots of the matching polynomial, Phys. Chem. Chem. Phys. 12 (2010), 5295–5306.
  * [5] W. Chen and C.Y. Ku, An analogue of the Gallai-Edmonds structure theorem for nonzero roots of the matching polynomial, J. Combin. Theory Ser. B 100 (2010), 119–127.
  * [6] Y.B. Choe, J.G. Oxley, A.D. Sokal, and D.G. Wagner, Homogeneous multivariate polynomials with the half-plane property, Adv. in Appl. Math. 32 (2004), 88–187, Special issue on the Tutte polynomial.
  * [7] G. Clark and J. Cooper, On the adjacency spectra of hypertrees, Electron. J. Combin. 25 (2018), $\\#$P2.48.
  * [8] J. Cooper and A. Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl. 436 (2012), 3268–3292.
  * [9] Y. Fan, T. Huang, Y. Bao, C. Zhuan-Sun, and Y. Li, The spectral symmetry of weakly irreducible nonnegative tensors and connected hypergraphs, Trans. Amer. Math. Soc. 372 (2019), 2213–2233.
  * [10] E.J. Farrell, An introduction to matching polynomials, J. Combin. Theory Ser. B 27 (1979), 75–86.
  * [11] S. Friedland, S. Gaubert, and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl. 438 (2013), 738–749.
  * [12] J. Friedman, The spectra of infinite hypertrees, SIAM J. Comput. 20 (1991), 951–961.
  * [13] J. Friedman and A. Wigderson, On the second eigenvalue of hypergraphs, Combinatorica 15 (1995), 43–65.
  * [14] J. Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, vol. 195, Memoirs of the AMS, 195 (2008), no.910.
  * [15] C.D. Godsil, Matchings and walks in graphs, J. Graph Theory 5 (1981), 285–297.
  * [16] C.D. Godsil and I. Gutman, On the theory of the matching polynomial, J. Graph Theory 5 (1981), 137–144.
  * [17] C.D. Godsil, Matching behaviour is asymptotically normal, Combinatorica 1 (1981), 369–376.
  * [18] C.D. Godsil, Spectra of trees, Annals of Discr. Math. 20 (1984), 151–159.
  * [19] C.D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993.
  * [20] I. Gutman, M. Milun, and M.N. Trinajstić, Non-parametric resonance energies of arbitrary conjugated systems, J. Amer. Chem. Soc. 99 (1977), 1692–1704.
  * [21] R. Hartshorne, Algebraic Geometry, Springer–Verlag, New York, 1977.
  * [22] C.s Hall, D. Puder, and W. F Sawin, Ramanujan coverings of graphs, Adv. Math. 323 (2018), 367–410.
  * [23] O.J. Heilmann and E.H. Lieb, Monomers and dimers, Phvs. Rev. Lett. 24 (1970), 1412–1414.
  * [24] O.J. Heilmann and E.H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190–232.
  * [25] S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439–561.
  * [26] T. Kálmán, A version of Tutte’s polynomial for hypergraphs, Adv. Math. 244 (2013), 823–873.
  * [27] T. Kálmán and A. Postnikov, Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs, Proc. Lond. Math. Soc. 114 (2017), 561–588.
  * [28] M. Khan and Y. Fan, On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs, Linear Algebra Appl. 480 (2015), 93–106.
  * [29] J. Lenz and D. Mubayi, Eigenvalues and linear quasirandom hypergraphs, Forum Math. Sigma 3 (2015), e2, 26 pp.
  * [30] B. Lass, Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs, J. Comb. Theory, Ser. B 102 (2012), 411–423.
  * [31] H. Li and B. Mohar, On the first and second eigenvalue of finite and infinite uniform hypergraphs, Proc. Amer. Math. Soc. 147 (2019), 933–946.
  * [32] L.-H. Lim, Singular values and eigenvalues of tensors: a variational approach, in: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, vol. 1, CAMSAP’05, pages 129–132, 2005.
  * [33] L. Liu and L. Lu, The $\alpha$-normal labeling method for computing the $p$-spectral radii of uniform hypergraphs, Linear Multilinear Algebra, 70 (2022), 1648–1672.
  * [34] L. Lovász and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, vol. 29, North Holland, 1986.
  * [35] Lovász and Pelikán, On the eigenvalues of trees, Period. Math. Hungar. 3 (1973), 175-182.
  * [36] L. Lu and S. Man, Connected hypergraphs with small spectral radius, Linear Algebra Appl. 509 (2016), 206–227.
  * [37] A. Lubotzky, R. Phillips and P. Sarnark, Ramanujan graphs, Combinatoria 8 (1988), 261–277.
  * [38] J.A. Makowsky, E.V. Ravve, and N.K. Blanchard, On the location of roots of graph polynomials, European J. Combin. 41 (2014), 1–19.
  * [39] A.W. Marcus, D.A. Spielman and N. Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. 182 (2015), 307–325.
  * [40] A. Mowshowitz, The characteristic polynomial of a graph, J. Combin. Theory Ser. B. 12 (1972), 177–193.
  * [41] L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005), 1302–1324.
  * [42] A.J. Schwenk, Almost all trees are cospectral, In Frank Harry, editor, New Directions in the Theory of Graphs, pages 275–307, New York, 1973. Academic Press.
  * [43] Y. Shi, M. Dehmer, X. Li, and I. Gutman, Graph Polynomials, CRC Press, 2016.
  * [44] R.P. Stanley, Log–concave and unimodal sequences in algebra, combinatorics, and geometry, in Graph Theory and its Applications: East and West, Annals of the New York Academy of Sciences 576, New York Acad. Sci., New York, 1989, pp. 500–535.
  * [45] L. Su, L. Kang, H. Li, and E. Shan, The matching polynomials and spectral radii of uniform supertrees, Electron. J. Combin. 25(4) (2018), $\\#$P4.13.
  * [46] I. Tomescu, Chromatic coefficients of linear uniform hypergraphs, J. Combin. Theory Ser. B 260 (1998), 229–235.
  * [47] Y. Yang and Q. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl. 31 (2010), 2517–2530.
  * [48] Y. Yang and Q. Yang, On some properties of nonnegative weakly irreducible tensors, arXiv: 1111.0713v2.
  * [49] R. Zhang and F. Dong, Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs, European J. Combin. 64 (2017), 138–151.
  * [50] W. Zhang, L. Kang, E. Shan, and Y. Bai, The spectra of uniform hypertrees, Linear Algebra Appl. 533 (2017), 84–94.
  * [51] J. Zhou, L. Sun, W. Wang, and C. Bu, Some spectral properties of uniform hypergraphs, Electron. J. Combin. 21(4) (2014), $\\#$P4.24.