The Matching Polynomial of the Path-Tree of the Complete Tripartite Graph ()
1. Introduction
Let
be a graph with
vertices. A matching of
is a spanning subgraph of
in which every component is either an isolated vertex or an isolated edge. A
-matching is a matching of
with exactly
edges. Reference [1] defines the matching polynomial of
as:
where
,
and
are weights assigned to vertices and edges, respectively, and
is the number of all
-matchings of
. If we set
, we obtain the matching polynomial defined in reference [2]:
The matching polynomial has been extensively studied not only in graph theory but also in combinatorics and statistical physics. For various properties of the matching polynomial, detailed information can be found in [1] [2]. Below, we introduce two specific properties:
1) If
, then
;
2) If
is a forest, then the matching polynomial of
coincides with its characteristic polynomial.
For a general graph
, Godsil [3] [4] showed that
is closely related to the characteristic polynomial of certain trees, namely the path-trees of
. By introducing path trees, Godsil proved that every matching polynomial divides the characteristic polynomial of some graph; hence, all roots of the matching polynomial are real. Similarly, using path-trees, Li et al. [5] proved that the roots of the
-polynomial of a graph are also real. Guo and Chen [6] discussed the matching polynomial of the path-tree for the complete graph. Recently, Che and Yan [7] also determined the matching polynomial of the path-tree for the complete bipartite graph. The study of matching polynomials for this type of tree not only deepens the theory of graph theory but also builds a bridge for the modeling and solution of practical problems, with applications in fields such as chemistry, computer science, and algorithm design, combinatorial optimization, and network theory. Therefore, path-trees constitute a class of trees worthy of investigation. In this article, we primarily present the matching polynomial of the path tree for the complete tripartite graph
.
2. Preliminary Knowledge
Definition 2.1 [7] [8] Given a graph
and a vertex
. The path-tree of
corresponding to
, denoted by
, is the tree with vertex set consisting of paths in
beginning from
, and two such paths are adjacent if one is the maximal subpath of the other.
Lemma 2.2 [7] [8] Let
denote the graph obtained by deleting vertex
from
. According to the definition, we obtain the following three properties:
1) If
is disconnected, then
is determined only by the connected component of
witch contains vertex
;
2) If
is a tree, then
for any
;
3) If the neighborhood set of
in
is
, then
.
Lemma 2.3 [3] [7] Given a vertex
of graph
, the matching polynomial of
.
Lemma 2.4 [7] For the bipartite graph
, where
,
,
, then the path-tree
matching polynomial is:
Lemma 2.5 [7] For the bipartite graph
, where
,
,
, then the path-tree
matching polynomial is:
3. Main Structure
Assume the vertex set of the complete tripartite graph
is
, where
,
,
, and
. We note that due to the symmetry of path trees, for any two vertices
or
, the path trees
and
are isomorphic, and similarly
and
are isomorphic. For simplicity, we will use
to denote
,
to denote
, and
to denote
.
Theorem 3.1 For the path-tree
, its matching polynomial
Proof. For any
. we have
then
Theorem 3.2 For the path-tree
, its matching polynomial
where
.
Proof. Now suppose that the result holds for any path-tree
with
,
, we have
From Lemma 2.3, we have

where
, then

and the theorem is proved.
Note:
1) For the obtained expression
in the formula, from Lemmas 2.3, 2.4, and 2.5, it is easy to know that
must divide
, We substitute the specific value of
, then we can obtain the specific expression of
.
Similarly,
can also obtain the specific expression.
2) For Theorem 2.3, we find that if
, then the polynomial would satisfy
, which is obviously not valid. Below, we present the polynomial when
.
Corollary 3.3 For the path-tree
, its matching polynomial
Proof. From Lemma 2.2 and Lemma 2.3, we have
When
,we can obtain the following corollary.
Corollary 3.4 For the path-tree
, its matching polynomial
Theorem 3.5 For the path-tree
, its matching polynomial
Proof. From Lemma 2.3, we have
where
, then we have
Comprehensively, from the above results, we can obtain
Corollary 3.6 For the path-tree
, its matching polynomial
Proof. From Corollary 3.3, it is easy to prove in a similar way that Corollary 3.6 is true.
4. Conclusions
By synthesizing Theorem 3.1, Theorem 3.2, and Theorem 3.5, we obtain
where
,
.
The core of studying the matching polynomials of this type of tree lies in revealing the intrinsic connection between the structural characteristics of graphs and the properties of matching polynomials. Through the analysis of complete bipartite graphs with specific symmetry, such as path trees, and by means of induction and recursive relations, the understanding of the polynomial theory of graphs can be deepened. Meanwhile, it provides methodological support for exploring the polynomial properties (such as characteristic polynomials and chromatic polynomials) of more complex graphs, such as
.
Funding
Innovation Project of Qinghai Minzu University (Project Number: 07M2024004).