The Matching Polynomial of the Path-Tree of the Complete Tripartite Graph K 1,s,t

Abstract

Let G be a complete tripartite graph with n vertices. Its vertex set is UVW , where | U |=1 , | V |=s , | W |=t , and this graph is denoted as K 1,s,t . Let T 1,s,t ω denote the path-tree corresponding to the vertex ωUVW . In this paper, we mainly present the matching polynomial of the path-tree T 1,s,t ω corresponding to the complete tripartite graph.

Share and Cite:

Ma, Y. (2025) The Matching Polynomial of the Path-Tree of the Complete Tripartite Graph K 1,s,t . Applied Mathematics, 16, 526-534. doi: 10.4236/am.2025.167030.

1. Introduction

Let G=( V,E ) be a graph with n vertices. A matching of G is a spanning subgraph of G in which every component is either an isolated vertex or an isolated edge. A t -matching is a matching of G with exactly t edges. Reference [1] defines the matching polynomial of G as:

M( G,W )= k0 p ( G,x ) n2k y k

where W=( x,y ) , x and y are weights assigned to vertices and edges, respectively, and p( G,k ) is the number of all k -matchings of G . If we set y=1 , we obtain the matching polynomial defined in reference [2]:

μ( G,x )= k=0 [ n/2 ] ( 1 ) k p( G,k ) x n2k

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 G= k=1 t G k , then μ( G,x )= k=1 t μ( G k ,x ) ;

2) If G is a forest, then the matching polynomial of G coincides with its characteristic polynomial.

For a general graph G , Godsil [3] [4] showed that μ( G,x ) is closely related to the characteristic polynomial of certain trees, namely the path-trees of G . 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 K 1,s,t .

2. Preliminary Knowledge

Definition 2.1 [7] [8] Given a graph G=( V,E ) and a vertex wV . The path-tree of G corresponding to w , denoted by T( G,w ) , is the tree with vertex set consisting of paths in G beginning from w , and two such paths are adjacent if one is the maximal subpath of the other.

Lemma 2.2 [7] [8] Let G\w denote the graph obtained by deleting vertex wV( G ) from G . According to the definition, we obtain the following three properties:

1) If G is disconnected, then T( G,w ) is determined only by the connected component of G witch contains vertex w ;

2) If G is a tree, then G=T( G,w ) for any wV( G ) ;

3) If the neighborhood set of w in G is Γ( w )={ w 1 , w 2 ,, w r } , then T( G,w )\w= k=1 r T( G\w, w k ) .

Lemma 2.3 [3] [7] Given a vertex w of graph G , the matching polynomial of T=T( G,w ) .

μ( T,x )=μ( G,x ) μ( T\w,x ) μ( G\w,x )

Lemma 2.4 [7] For the bipartite graph K s,t , where uU , | U |=s , β s,t k = j=k+1 s1 j( ts+j ) , then the path-tree T s,t u matching polynomial is:

μ( T s,t u ,x )=μ( K s,t ,x ) k=1 s1 μ ( K k,ts+k ,x ) t( ks ) β s,t k μ ( K k,ts+k+1 ,x ) t( ts+k ) ts+k+1 β s,t k

Lemma 2.5 [7] For the bipartite graph K s,t , where vU , | U |=s , β s,t k = j=k+1 s1 j( ts+j ) , then the path-tree T s,t u matching polynomial is:

μ( T s,t v ,x )=μ( K s,t ,x )μ ( K s,t1 ,x ) s1 k=1 s1 μ ( K k,ts+k1 ,x ) s( k1 )( ts+k ) β s,t k μ ( K k,ts+k ,x ) s( ts+k1 ) β s,t k

3. Main Structure

Assume the vertex set of the complete tripartite graph K 1,s,t is UVW , where | U |=1 , | V |=s , | W |=t , and st>1 . We note that due to the symmetry of path trees, for any two vertices v, v V or w, w W , the path trees T( K 1,s,t ,v ) and T( K 1,s,t , v ) are isomorphic, and similarly T( K 1,s,t ,w ) and T( K 1,s,t , w ) are isomorphic. For simplicity, we will use T 1,s,t u to denote T( K 1,s,t ,u ) , T 1,s,t v to denote T( K 1,s,t ,v ) , and T 1,s,t w to denote T( K 1,s,t ,w ) .

Theorem 3.1 For the path-tree T 1,s,t u ( t>s>1 ) , its matching polynomial

μ( T 1,s,t u ,x )=μ( K 1.s.t ,x ) μ ( T s,t v ,x ) s μ ( T s,t w ,x ) t μ( K s,t )

Proof. For any T 1,s,t ( t>s>1 ) . we have

μ( T 1,s,t u \u,x )=μ ( T s,t v ,x ) s μ( T s,t w ,x )

then

μ( T 1,s,t u ,x )= μ( K 1,s,t ,x )μ( T 1,s,t u \u,x ) μ( K 1,s,t \u,x ) =μ( K 1.s.t ,x ) μ ( T s,t v ,x ) s μ ( T s,t w ,x ) t μ( K s,t )

Theorem 3.2 For the path-tree T 1,s,t v ( t>s>1 ) , its matching polynomial

μ( T 1,s,t v ,x )=μ( K 1,s,t ,x ) k=1 s1 μ ( K 1,k,ts+k ,x ) tk β 1,s,t k μ ( K 1,k,ts+k+1 ,x ) t β 1,s,t k [ μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k μ( K k,ts+k ,x ) ] t β 1,s,t k [ μ ( T k,ts+k+1 v ,x ) k μ ( T k,ts+k+1 w ,x ) ts+k+1 μ( K k,ts+k+1 ,x ) ] t ts+k+1 β 1,s,t k

where β 1,s,t k = j=k+1 s1 j( ts+j ) .

Proof. Now suppose that the result holds for any path-tree T 1,m,n v with m<s , nm , we have

μ( T 1,s1,t1 v ,x )=μ( K 1,s1,t1 ,x ) k=1 s2 μ ( K 1,k,ts+k ,x ) ( t1 )k β 1,s1,t1 k μ ( K 1,k,ts+k+1 ,x ) ( t1 ) β 1,s1,t1 k [ μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k μ( K k,ts+k ,x ) ] ( t1 ) β 1,s1,t1 k [ μ ( T k,ts+k+1 v ,x ) k μ ( T k,ts+k+1 w ,x ) ts+k+1 μ( K k,ts+k+1 ,x ) ] t1 ts+k+1 β 1,s1,t1 k

From Lemma 2.3, we have

where β 1,s,t k = j=k+1 s1 j( ts+j ) =( t1 )( s1 ) β 1,s1,t1 k , then

and the theorem is proved.

Note:

1) For the obtained expression μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k μ( K k,ts+k ,x ) in the formula, from Lemmas 2.3, 2.4, and 2.5, it is easy to know that μ( K k,ts+k ,x ) must divide μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k , We substitute the specific value of k , then we can obtain the specific expression of μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k μ( K k,ts+k ,x ) .

Similarly, μ ( T k,ts+k+1 v ,x ) k μ ( T k,ts+k+1 w ,x ) ts+k+1 μ( K k,ts+k+1 ,x ) can also obtain the specific expression.

2) For Theorem 2.3, we find that if s=1 , then the polynomial would satisfy μ( T 1,s,t v ,x )=μ( K 1,s,t ,x ) , which is obviously not valid. Below, we present the polynomial when s=1 .

Corollary 3.3 For the path-tree μ( T 1.1.t u ,x ) , its matching polynomial

μ( T 1.1.t u ,x )=μ( K 1,1,t ,x )μ ( K 1,t ,x ) t μ ( K 1,t1 ,x ) t1

Proof. From Lemma 2.2 and Lemma 2.3, we have

μ( T 1.1.t u ,x )=μ( K 1,1,t ,x ) μ( T 1,t v ,x )μ ( T 1,t w ,x ) t μ( K 1,t ,x ) =μ( K 1,1,t ,x ) μ( K 1,t ,x ) μ( K 1,t ,x ) [ μ( K 1,t ,x )μ( T 1,t1 v ,x ) μ( K 1,t1 ,x ) ] t =μ( K 1,1,t ,x ) [ μ( K 1,t ,x )μ( K 1,t1 v ,x ) μ( K 1,t1 ,x ) ] t =μ( K 1,1,t ,x )μ ( K 1,t ,x ) t μ ( K 1,t1 v ,x ) t1

When s=t ,we can obtain the following corollary.

Corollary 3.4 For the path-tree T 1,s,s ω ,ωVW , its matching polynomial

μ( T 1,s,s v ,x )=μ( T 1,s,s w ,x ) =μ( K 1,s,s ,x ){ k=1 s1 μ ( K 1,k,k ,x ) k μ( K 1,k,k+1 ,x ) [ μ ( T k,k v ,x ) k μ ( T k,k w ,x ) k μ( K k,k ,x ) ] [ μ ( T k,k+1 v ,x ) k μ ( T k,k+1 w ,x ) k+1 μ( K k,k+1 ,x ) ] 1 k+1 } t j=k+1 s1 j 2

Theorem 3.5 For the path-tree T 1,s,t w ( t>s>1 ) , its matching polynomial

μ( T 1,s,t w ,x )=μ( K 1,s,t ,x )μ ( K 1,s,t1 ,x ) s μ ( T s,t1 v ,x ) s μ ( T s,t1 w ,x ) t1 μ( K s,t1 ,x )

k=1 s1 μ ( K 1,k,ts+k ,x ) s( ts+k ) β 1,s,t k μ ( K 1,k,ts+k1 ,x ) sk( ts+k ) β 1,s,t k [ μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k μ( K k,ts+k ,x ) ] s β 1,s,t k [ μ ( T k,ts+k1 v ,x ) k μ ( T k,ts+k1 w ,x ) ts+k1 μ( K k,ts+k1 ,x ) ] s( ts+k ) β 1,s,t k

Proof. From Lemma 2.3, we have

μ( T 1,s,t w ,x )= μ( K 1,s,t ,x )μ( T 1,s,t w \w,x ) μ( K 1,s,t \w,x ) =μ( K 1,s,t ,x ) μ( T 1,s,t1 u \u,x )μ ( T 1,s,t1 v ,x ) s μ( K 1,s,t1 ,x ) =μ( K 1,s,t ,x ) μ ( T s,t1 v ,x ) s μ ( T s,t1 w ,x ) t1 μ( K s,t1 ,x ) μ ( T 1,s,t1 v ,x ) s

where β 1,s,t k = j=k+1 s1 j ( ts+j )= t1 ts+k β 1,s,t1 k , then we have

μ( T 1,s,t1 v ,x )=μ( K 1,s,t1 ,x ) k=1 s1 μ ( K 1,k,ts+k1 ,x ) ( t1 )k β 1,s,t1 k μ ( K 1,k,ts+k ,x ) ( t1 ) β 1,s,t1 k [ μ ( T k,ts+k1 v ,x ) k μ ( T k,ts+k1 w ,x ) ts+k1 μ( K k,ts+k1 ,x ) ] ( t1 ) β 1,s,t1 k [ μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k μ( K k,ts+k ,x ) ] t1 ts+k β 1,s,t1 k

Comprehensively, from the above results, we can obtain

μ( T 1,s,t w ,x )=μ( K 1,s,t ,x )μ ( K 1,s,t1 ,x ) s μ ( T s,t1 v ,x ) s μ ( T s,t1 w ,x ) t1 μ( K s,t1 ,x ) k=1 s1 μ ( K 1,k,ts+k ,x ) s( ts+k ) β 1,s,t k μ ( K 1,k,ts+k1 ,x ) sk( ts+k ) β 1,s,t k [ μ ( T k,ts+k v ,x ) k μ ( T k,ts+k w ,x ) ts+k μ( K k,ts+k ,x ) ] s β 1,s,t k [ μ ( T k,ts+k1 v ,x ) k μ ( T k,ts+k1 w ,x ) ts+k1 μ( K k,ts+k1 ,x ) ] s( ts+k ) β 1,s,t k

Corollary 3.6 For the path-tree μ( T 1.s.1 w ,x ) , its matching polynomial

μ( T 1.s.1 w ,x )=μ( T 1.1.s u ,x )=μ( K 1,1,s ,x )μ ( K 1,s ,x ) s μ ( K 1,s1 ,x ) s1

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

μ( T 1,s,t ω ,x )=μ( K 1,s,t ,x )

{ μ ( T s,t v ,x ) s μ ( T s,t w ,x ) t μ( K s,t ) , ωU; { k=1 s1 μ ( K 1,k,α+k ,x ) k μ( K 1,k,α+k+1 ,x )[ μ ( T k,α+k v ,x ) k μ ( T k,α+k w ,x ) α+k μ( K k,α+k ,x ) ] [ μ ( T k,α+k+1 v ,x ) k μ ( T k,α+k+1 w ,x ) α+k+1 μ( K k,α+k+1 ,x ) ] 1 α+k+1 } t β 1,s,t k , ωV; μ ( K 1,s,t1 ,x ) s μ ( T s,t1 v ,x ) s μ ( T s,t1 w ,x ) t1 μ( K s,t1 ,x ) k=1 s1 μ ( K 1,k,α+k ,x ) s( α+k ) β 1,s,t k { μ ( K 1,k,α+k1 ,x ) k( α+k ) [ μ ( T k,α+k v ,x ) k μ ( T k,α+k w ,x ) α+k μ( K k,α+k ,x ) ] [ μ ( T k,α+k1 v ,x ) k μ ( T k,α+k1 w ,x ) ts+k1 μ( K k,α+k1 ,x ) ] α+k } s β 1,s,t k , ωW.

where α=ts , β 1,s,t k = j=k+1 s1 j( α+j ) .

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 K r,s,t .

Funding

Innovation Project of Qinghai Minzu University (Project Number: 07M2024004).

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1] Farrell, E.J. (1979) An Introduction to Matching Polynomials. Journal of Combinatorial Theory, Series B, 27, 75-86.
https://doi.org/10.1016/0095-8956(79)90070-4
[2] Godsil, C.D. and Gutman, I. (1981) On the Theory of the Matching Polynomial. Journal of Graph Theory, 5, 137-144.
https://doi.org/10.1002/jgt.3190050203
[3] Godsil, C.D. (1981) Matchings and Walks in Graphs. Journal of Graph Theory, 5, 285-297.
https://doi.org/10.1002/jgt.3190050310
[4] Godsil, C.D. (1993) Algebraic Combinatorics. Chapman and Hall.
[5] Li, X., Zhao, H. and Wang, L. (2003) A Complete Solution to a Conjecture on the Β-Polynomials of Graphs. Journal of Mathematical Chemistry, 33, 189-193.
https://doi.org/10.1023/a:1024738623798
[6] Guo, M. and Chen, H. (2024) The Matching Polynomial of the Path-Tree of a Complete Graph. Discrete Applied Mathematics, 359, 244-249.
https://doi.org/10.1016/j.dam.2024.08.005
[7] Chen, H. and Yuan, Y. (2025) Matching Polynomials of Path-Trees of a Complete Bipartite Graph. Discrete Applied Mathematics, 372, 173-179.
https://doi.org/10.1016/j.dam.2025.04.014
[8] Cvetković, D.M., Gutman, I., Doob, M. and Torgašev, A. (1988) Recent Results in the Theory of Graph Spectra. North Holland.

Copyright © 2025 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.