ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.24447 J. Algebra Comb. Discrete Appl. 4(1) • 1–11 Received: 5 April 2015 Accepted: 10 April 2016 Journal of Algebra Combinatorics Discrete Structures and Applications On the matching polynomial of hypergraphs∗ Research Article Zhiwei Guo, Haixing Zhao, Yaping Mao Abstract: The concept of the matching polynomial of a graph, introduced by Farrell in 1979, has received con- siderable attention and research. In this paper, we generalize this concept and introduce the matching polynomial of hypergraphs. A recurrence relation of the matching polynomial of a hypergraph is ob- tained. The exact matching polynomials of some special hypergraphs are given. Further, we discuss the zeros of matching polynomials of hypergraphs. 2010 MSC: 05C31, 05C65, 05C70 Keywords: Hypergraph, Matching polynomial, Line-graph, Independence polynomial 1. Introduction Hypergraphs are systems of finite sets. With the development of computer science, this branch of mathematics has developed rapidly during the late twentieth century. Hypergraphs model more general types of relations than graphs. For more results on hypergraph, we refer to [1, 2, 5, 11–13]. The matching polynomial of a graph was introduced by Farrell in 1979. For more details on the matching polynomial of a graph, we refer to [3, 4, 6, 7, 9, 15, 21]. An h-uniform hypergraph is a pair H = (V ; E), where V = V (H) is a finite set of vertices, and E = E(H) ⊆ ( V h ) is a family of h-element subsets of V called hyperedges. All hypergraphs considered in this paper are h-uniform hypergraphs. A simple hypergraph is a hypergraph H = (V ; E) such that ei ⊆ ej if and only if i = j. A hypergraph is linear if it is simple and |ei ∩ej| ≤ 1, for all ei, ej ∈ E where ∗ Supported by the National Science Foundation of China (Nos. 61164005, 11161037, 11101232, 61440005 and 11461054) and the Program for Changjiang Scholars and Innovative Research Team in Universities (No. IRT1068), the Research Fund for the Chunhui Program of Ministry of Education of China (No. Z2014022) and the Nature Science Foundation from Qinghai Province (Nos. 2013-Z-Y17, 2014-ZJ-721, 2015-ZJ-905 and 2014-ZJ-907). Zhiwei Guo, Yaping Mao (Corresponding Author); Department of Mathematics, Qinghai Normal University, Xining, Qinghai 810008, China (email: guozhiweic@yahoo.com, maoyaping@ymail.com). Haixing Zhao; School of Computer, Qinghai Normal University, Xining, Qinghai 810008, China (email: h.x.zhao@163.com). 1 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 i 6= j. Given V ′ ⊆ V , the subhypergraph H′ is the hypergraph H′ = (V ′, E′ = (ej)j∈J) such that for all ej ∈ E′, ej ⊆ V ′. A matching of H consists of isolated vertices and hyperedges only. A k-matching of H contains k disjoint hyperedges in E(H). Let M be a k-matching in H and let us assign “weights” w1 and w2 to each vertex and edge, respectively in M. Let us associate the weight wn−kh1 w k 2 with M. Then if ak is the number of k- matchings in H, the total weight of the k-matchings in H will be a akw n−kh 1 w k 2. By summing the weights of all the k-matchings in H, for all possible values of k, we will obtain a polynomial in w1 and w2. This polynomial is called the matching polynomial of H. Denote by it M(H; w), i.e. M(H; w) = bn/hc∑ k=0 akw n−kh 1 w k 2, where w = (w1, w2) is called the weight vector associated with the matching polynomial. If we put w1 = w2 = w, then the resulting polynomial in w will be called the simple matching polynomial of H, M(H; w) = bn/hc∑ k=0 akw n−k(h−1). The matching polynomials of hypergraphs may also be regarded as a special type of multivariate hyperedge elimination chromatic polynomials first investigated by White [20]. This paper is organized as follows. In section 2, we present a well-known fundamental theorem for the matching polynomials of hypergraphs which we use in section 3, to obtain recursively the formulae for the matching polynomials of some classes of hypergraphs. In general, these formulae are intractable, giving our choice of these particular hypergraphs which are much easier to manipulate. We hope these results can inspire further computations of these polynomials. In the last section, we discuss the zeros of these polynomials when compared to their graphs counterparts. 2. The fundamental theorem for matching polynomials Firstly, we define two graphs operations which will be used later. Deletion of hyperedge e, i.e. e is removed and the vertices of e are still retained. Contraction of hyperedge e, i.e. e is removed and all vertices of e and hyperedges adjacent to e are removed. Since matchings consist of isolated vertices and hyperedges, the inclusion of an hyperedge in a matching implies the exclusion of all hyperedges adjacent to it. By partitioning the set of matchings in the hypergraph into two classes: (i) those containing a given hyperedge e and (ii) those not containing e, the following result is immediate. Theorem 2.1. Let H be a hypergraph containing a hyperedge e. Let H′ be the hypergraph obtained from H by deleting e, and H′′ be the hypergraph obtained from H by contracting e. Then M(H; w) = M(H′; w) + w2M(H ′′; w). The fundamental recurrence relation of Theorem 2.1 firstly appeared in [7], for graphs and it is widely used. Other versions of this recursion also appeared in [18]. Proposition 2.2. Let H be a hypergraph, and let H1 and H2 be two subhypergraphs of H such that V (H1)∩V (H2) = ∅ and H1 ∪H2 = H. Then M(H; w) = M(H1; w) ·M(H2; w). The line-graph of H is the graph L(H) = (V ′; E′) such that: (i) V ′ = E when H is without repeated hyperedge; 2 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 (ii) {ei, ej}∈ E′(i 6= j) if and only if ei ∩ej 6= ∅. The first formal definition of the independence polynomial appears to be due to Gutman and Harary [10]. The independence polynomial of a graph G will be denoted by I(G, x), i.e. I(G; x) = α(G)∑ k=0 akx k, where ak is the number of independence sets of G with exactly k vertices. For more details on the independence polynomial, we refer to [14, 16, 17, 19]. By the above definition, one can see that the coefficients of the matching polynomial of a simple hypergraph and the coefficients of the independence polynomial of its line-graph are identical. Since the line-graph of a hypergraph H is a simple graph, it follows that the matching polynomial of a hypergraph can be obtained by the known independence polynomial of its line-graph. The following proposition gives us a method to calculate the matching polynomial of a given hypergraph. Note that I(L(H); x) is the independence polynomial of L(H). Then the following proposition is immediate. Proposition 2.3. Let I(L(H); x) = α(L(H))∑ k=0 akx k be the independence polynomial of L(H). Then the matching polynomial of H is M(H; w) = bn/hc∑ k=0 akw n−kh 1 w k 2. 3. Matching polynomials of some special hypergraphs In this section, we discuss the matching polynomials of hyperpaths, hyperstars, hypercycles, complete h-uniform hypergraphs and two new hypergraphs HW` and HS`. 3.1. Matching polynomials of hyperpaths and hyperstars A hyperpath in H from x to y, is a vertex-hyperedge alternating sequence: x = x1, e1, x2, e2, . . . , xs, es, xs+1 = y such that • x1, x2, . . . , xs, xs+1 are distinct vertices with the possibility that x1 = xs+1; • e1, e2, . . . , es are distinct hyperedges; • xi, xi+1 ∈ ei, for all i ∈{1, 2, . . . , s}. If x = x1 = xs+1 = y, then the hyperpath is called a hypercycle. Here and throughout, the length is equal to the number of hyperedges. Let P` be a linear hyperpath with length of `. We can apply Theorem 2.1 to P` by operating for a terminal hyperedge. This immediately yields the recurrence relation. Proposition 3.1. Let P` be a linear hyperpath with length of ` (` > 1). Then M(P`; w) = w (h−1) 1 M(P`−1; w) + w (h−2) 1 w2M(P`−2; w). (1) 3 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 Furthermore, the following expression of M(P`; w) can be obtained. Theorem 3.2. Let P` be a linear hyperpath with length of ` (` > 1). Then M(P`; w) = bn/hc∑ k=0 ( ` + 1−k k ) w (n−kh) 1 w k 2, (2) where n denotes the order of P`. Proof. By Proposition 3.1, we have M(P`; w) = w (h−1) 1 M(P`−1; w) + w (h−2) 1 w2M(P`−2; w). For convenience, we use p(i) to denote M(Pi; w). Then p(0) = w1, p(1) = w2 + w h 1 . We can obtain the generating function for M(P`; w) from Equation (1). Let g(x) be the generating function of M(P`; w). g(x) = p(0) + p(1)x + p(2)x 2 + p(3)x 3 + . . . −w(h−1)1 xg(x) = −w (h−1) 1 p(0)x−w (h−1) 1 p(1)x 2 − w(h−1)1 p(2)x3 + . . . −w(h−2)1 w2x2g(x) = −w (h−2) 1 w2p(0)x 2 −w(h−2)1 w2p(1)x3 + . . . By Equation (1), we can obtain the generating function, i.e. g(x) = w1 + w2x 1−w(h−1)1 x−w (h−2) 1 w2x 2 . (3) By expanding Equation (3) as the sum of an infinite geometrical progression and extracting the coefficient of x`, we can obtain the matching polynomials of hyperpath P`, i.e. M(P`; w) = bn/hc∑ k=0 ( ` + 1−k k ) w (n−kh) 1 w k 2, where n denotes the order of P`. Remark 3.3. In fact, we can also prove Theorem 3.2 by the idea from Proposition 2.3. Note that the matching polynomial of a hypergraph and the independence polynomial of its line-graph are identical. Observe that the line-graph of P` is the path P with ` vertices. Song et al. [17] obtained the independence polynomial of the path P with n vertices, i.e. I(Pn; x) = b(n+1)/2c∑ s=0 ( n + 1−s s ) xs. A hyperstar S is a family of hyperedges containing a given vertex. Let S` be a linear hyperstar with ` edges. Since any two edges of S are intersecting, a matching of a hyperstar has at most one edge. So, we can obtain the matching polynomials of hyperstars. Proposition 3.4. The matching polynomial of S` is M(S`; w) = 1 + `w (n−h) 1 w2, where n denotes the order of S`. 4 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 3.2. Matching polynomials of hypercycles Let C` be a linear hypercycle with length of `. We apply Theorem 2.1 to C` by operating for an arbitrarily hyperedge. This immediately yields the recurrence relation. Theorem 3.5. Let C` be a linear hypercycle with length of ` (` > 2). Then M(C`; w) = w (h−2) 1 M(P`−1; w) + w 2(h−2) 1 w2M(P`−3; w). (4) Theorem 3.6. Let C` be a linear hypercycle with length of ` (` > 2). Then M(C`; w) = w n 1 + bn/hc∑ k=1 ` k ( `−1−k k −1 ) w (n−kh) 1 w k 2, where n denotes the order of C`. Proof. From Theorem 3.5, we have M(C`; w) = w (h−2) 1 M(P`−1; w) + w 2(h−2) 1 w2M(P`−3; w). By Equation (2), we can obtain the expression of M(P`−1; w) and M(P`−3; w) as follows. M(P`−1; w) = b[(`−1)·(h−1)+1]/hc∑ k=0 ( `−k k ) w ([(`−1)·(h−1)+1]−kh) 1 w k 2, M(P`−3; w) = b[(`−3)·(h−1)+1]/hc∑ k=0 ( `−2−k k ) w ([(`−3)·(h−1)+1]−kh) 1 w k 2. Therefore, we have M(C`; w) = w (h−2) 1 b[(`−1)·(h−1)+1]/hc∑ k=0 ( `−k k ) w ([(`−1)·(h−1)+1]−kh) 1 w k 2 +w 2(h−2) 1 w2 b[(`−3)·(h−1)+1]/hc∑ k=0 ( `−2−k k ) w ([(`−3)·(h−1)+1]−kh) 1 w k 2 = w [(`−1)·(h−1)+1]+h−2 1 + b[(`−1)·(h−1)+1]/hc∑ k=1 ( `−k k ) w ([(`−1)·(h−1)+1]−kh+h−2) 1 w k 2 + b[(`−3)·(h−1)+1]/hc∑ k′=1 ( `−1−k′ k′ −1 ) w ([(`−3)·(h−1)+1]−k′h+3h−4) 1 w k′ 2 = w `(h−1) 1 + b`(h−1)/hc∑ k=1 ( ( `−k k ) + ( `−1−k k −1 ) )w `(h−1)−kh 1 w k 2 = wn1 + bn/hc∑ k=1 ` k ( `−k −1 k −1 ) wn−kh1 w k 2 Furthermore, we obtain the recurrence relation involving the matching polynomials of hypercycles only. 5 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 Theorem 3.7. Let C` be a linear hypercycle with length of ` (` ≥ 5). Then M(C`; w) = w (h−1) 1 M(C`−1; w) + w (h−2) 1 w2M(C`−2; w). Proof. From Theorem 3.5, we have M(C`; w) = w (h−2) 1 M(P`−1; w) + w 2(h−2) 1 w2M(P`−3; w) (` ≥ 3). (5) By Proposition 3.1, we can obtain the following equalities: M(P`−1; w) = w (h−1) 1 M(P`−2; w) + w (h−2) 1 w2M(P`−3; w) (6) and M(P`−3; w) = w (h−1) 1 M(P`−4; w) + w (h−2) 1 w2M(P`−5; w). (7) By Equations (5), (6) and (7), we have M(C`; w) = w (h−1) 1 [w (h−2) 1 M(P`−2; w) + w 2(h−2) 1 w2M(P`−4; w)] +w (h−2) 1 w2[w (h−2) 1 M(P`−3; w) + w 2(h−2) 1 w2M(P`−5; w)]. From Theorem 3.5, we have M(C`; w) = w (h−1) 1 M(C`−1; w) + w (h−2) 1 w2M(C`−2; w). Remark 3.8. In fact, we can also prove Theorem 3.6 by the idea from Proposition 2.3. Note that the coefficients of the matching polynomial of a simple hypercycle and the coefficients of the independence polynomial of its line-graph are identical. Observe that the line-graph of a cycle C` is also a cycle with ` vertices. Song et al. [17] obtained the independence polynomials of the cycle C with n vertices, i.e. I(Cn; x) = 1 + bn/2c∑ s=1 n s ( n−1−s s−1 ) xs. 3.3. Matching polynomial of a complete h-uniform hypergraphs A complete h-uniform hypergraph is a hypergraph which has all h-subsets of V as hyperedges. Let Khn be a complete h-uniform hypergraph. We can obtain the matching polynomial of a complete h-uniform hypergraph by applying the Principle of Combinatorial Enumeration. Proposition 3.9. Let Khn be a complete h-uniform hypergraph with n vertices. Then M(Khn; w) = bn/hc∑ k=0 akw (n−kh) 1 w k 2, where a0 = 1, ak = ∏k−1 i=0 ( n−ih h ) k! (k ≥ 1). 6 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 Proof. We choose h vertices from the vertex set of Khn to form the first hyperedge e1 of the k-matching. Note that we have ( n h ) ways to do it. There are n − h remaining vertices in Khn −{e1}. We continue to choose h vertices from the vertex set of Khn −{e1} to form a new hyperedge of the k-matching, say e2. Note that we have ( n−h h ) ways to do it. There are n−2h remaining vertices in Khn −{e1, e2}. Continue the process by the same method. Then we can find e1, e2, . . . , ek such that ei ∩ ej = ∅ (1 ≤ i 6= j ≤ k). Since the hyperedges of a k-matching are unordered, the coefficient ak of M(Khn; w) is∏k−1 i=0 ( n−ih h ) k! for the special case, a0 = 1. 3.4. Matching polynomials of HW` and its dual A centipede is a tree denoted by Wn = (A ∪ B, E) (n ≥ 1), where A ∪ B is its vertex set, A = {a1, . . . , an}, B = {b1, . . . , bn}, and the edge set E = {aibi : 1 ≤ i ≤ n}∪{bibi+1 : 1 ≤ i ≤ n−1} (see Figure 1(a)). b1 b2 b3 bn−1 bn a1 a2 a3 an−1 an (a) e1 e2 eℓ−1 eℓ e′1 e ′ 2 e′ℓ−1 e ′ ℓ (b) Figure 1. (a) Centipede Wn, (b) Hypergraph HW`. We define a new hypergraph HW` = (V ; E1 ∪ E2) such that ei ∈ E1, ei ′ ∈ E2 and ei ∩ei ′ 6= ei ∩ei+1 6= ∅, where 1 ≤ i ≤ `−1 (see Figure 1(b)). Lemma 3.10. [14] Let I(W`; x) be the independence polynomial of W`. Then I(W`; x) = ∑̀ s=0 tsx s, where ts = s∑ j=0 ( `− j `−s )( ` + 1− j j ) , s ∈{0, 1, . . . , `}. Proposition 3.11. Let M(HW`; w) be the matching polynomial of HW` with n vertices. Then M(HW`; w) = bn/hc∑ k=0 akw (n−kh) 1 w k 2, 7 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 where ak = k∑ j=0 ( `− j `−k )( ` + 1− j j ) . Proof. Observe that the line-graph of HW` is a centipede W`. From Lemma 3.10, we have I(W`; x) = ∑̀ s=0 tsx s, where ts = s∑ j=0 ( `− j `−s )( ` + 1− j j ) , s ∈{0, 1, . . . , `}. By Proposition 2.3 and the above formula, we can obtain the matching polynomial of HW`, i.e. M(HW`; w) = bn/hc∑ k=0 akw (n−kh) 1 w k 2, where ak = k∑ j=0 ( `− j `−k )( ` + 1− j j ) . Remark 3.12. According to our discussion, we observe that the coefficients of M(P`; w) are equivalent to those of a simple path of length `. Likewise, the coefficients of M(C`; w) are the same as those of a simple cycle of length `. However, we are unable to find an equivalent matching polynomial for hypergraph HW`, giving the importance of this results and the next one. Let K` = (V, E) denote a simple complete graph with ` vertices. Set V (K`) = {vi : 1 ≤ i ≤ `}. Let K∗` be a simple graph obtained from K` by adding ` new vertices {u1, u2, · · · , u` and the edges {uivi : 1 ≤ i ≤ `}. We now define a new hypergraph HS` = (V ; E1 ∪E2) satisfying the following conditions (see Figure 2). (1) E1 = {e1, e2, · · · , e`} and E2 = {e′1, e′2, · · · , e′`}; (2) The hypergraph induced by the edges in E1 is a linear hyperstar; (3) For ei ∈ E1 and e′j ∈ E2, ei ∩ej ′ 6= ∅ for i = j, ei ∩ej ′ = ∅, for i 6= j. Lemma 3.13. [14] Let I(K∗` ; x) be the independence polynomial of K ∗ ` , then I(K∗` ; x) = (1 + x) `−1 · [1 + (` + 1)x]. Proposition 3.14. Let M(HS`; w) be the matching polynomial of HS`, then M(HS`; w) = (`−1)wn1 + bn/hc∑ k=1 [ ( `−1 s ) + ( `−1 s−1 ) ]w (n−kh) 1 w k 2. 8 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 e1 e2 eℓ−1 eℓ e ′ 2 e ′ 1 e ′ ℓ−1 e ′ ℓ Figure 2. Hypergraph HS`. Proof. We know that the line-graph of HS` is a K∗` . From Lemma 3.13, we have I(K ∗ ` ; x) = (1 + x)`−1 · [1 + (` + 1)x]. By simplifying the above equation, we obtain the following equation. I(K∗` ; x) = (`−1) + ∑̀ s=1 [( `−1 s ) + ( `−1 s−1 )] xs. By the Propostion 2.3 and the above equation, we can obtain the matching polynomial of HS`, i.e. M(HS`; w) = (`−1)wn1 + bn/hc∑ k=1 [( `−1 s ) + ( `−1 s−1 )] w (n−kh) 1 w k 2. 4. Zeros of matching polynomials of a hypergraphs It is well known that the zeros of matching polynomial of any connected graph are all real numbers [8]. However, we observe from an example that this assertion does not hold true for hypergraphs, in general. To the best of our knowledge, this case is unknown. Consider the hypergraph H as shown in Figure 3(a). Observe that the line-graph of H is the next simple graph L(H) (see Figure 3(b)). v1 v2 v3 v4 v5v6 v7 e1 e2 e3 e4 e5e6 e7 (a) (b) Figure 3. (a) Hypergraph H, (b) the line-graph of H. Proposition 4.1. [14] Let G = (V, E) be a graph, U ⊂ V be such that G[U] is a complete subgraph of G and I(G, x) be the independence polynomial of G. Then I(G, x) = I(G−U, x) + x ∑ v∈U I(G−N[v], x), where N(v) = {w : vw ∈ E(G)}, N[v] = N(v) ⋃ {v}. 9 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 Proposition 4.2. [19] Let En be an edgeless graph on n vertices, I(En, x) be the independence polynomial of En. Then I(En, x) = (1 + x) n. From Proposition 4.1 and Proposition 4.2, we obtain the independence polynomial of L(H), i.e. I(L(H), x) = x5 + 5x4 + 12x3 + 14x2 + 7x + 1. By Proposition 2.3, we obtain the matching polynomial of H, i.e. M(H; w) = w15 + 7w13 + 14w11 + 12w9 + 5w7 + w5. Using the MATLAB software, we obtain from M(H; w) the following zeros: 0, 0, 0, 0, 0, -0.0000 + 2.0893i, -0.0000 - 2.0893i, -0.2839 + 0.6309i, -0.2839 - 0.6309i, 0.2839 + 0.6309i, 0.2839 - 0.6309i, 0.0000 + 1.0000i, 0.0000 - 1.0000i, -0.0000 + 1.0000i, -0.0000 - 1.0000i. Thus, we can obtain the fact that the zeros of a matching polynomial of a hypergraph are not necessarily all real numbers. Acknowledgment: The authors are very grateful to the editor and the referees’ valuable comments and suggestions, which helped to improve the presentation of this paper. References [1] N. Alon, J. Kim, J. Spencer, Nearly perfect matchings in regular simple hypergraphs, J. Isr. J. Math. 100(1) (1997) 171–187. [2] A. Bretto, Hypergraph Theory, Springer, 2013. [3] R. A. Beezer, E. J. Farrell, The matching polynomial of a regular graph, Discrete Math. 137(1–3) (1995) 7–18. [4] H. Bian, F. Zhang, G. Wang, H. Yu, Matching polynomials for chains of cycles, Discrete Math. 311(4) (2011) 319–323. [5] Y. H. Chan, L. C. Lau, On linear and semidefinite programming relaxations for hypergraph matching, Math. Program. Ser A 135(1) (2012) 123–148. [6] F. M. Dong, A new expression for matching polynomials, Discrete Math. 312(4) (2012) 803–807. [7] E. J. Farrell, A introduction to matching polynomials, J. Combin. Theory Ser. B 27(1) (1979) 75–86. [8] C. D. Godsil, Algebraic Combinatorics, New York. London: Chapman and Hall, 1993. [9] C. D. Godsil, I. Gutman, On the theory of the matching polynomial, J. Graph Theory 5(2) (1981) 137–145. [10] I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97–106. [11] J. Han, Near perfect matchings in k−uniform hypergraphs, Comb. Probab. Comp. 24(5) (2015) 723–732. [12] H. Huang, P. S. Loh, B. Sudakov, The size of a hypergraph and its matching number, Comb. Probab. Comp. 21(3) (2012) 442–450. [13] P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, Mem. Amer. Math. Soc. 2015. [14] V. E. Levit, E. Mandrescu, The independence polynomial of a graph–a survey, Proc. 1st Int. Conf. Algebraic Informatics, Thessaloniki, Oct. 20–23, 2005 (eds. S. Bozapalidis, A. Kalampakas, G. Ra- honis), Thessaloniki, Greece: Aristotle University (2005), 233–254. [15] J. P. Mcsorley, P. Feinsilver, Multivariate matching polynomials of cyclically labelled graphs, Discrete Math. 309(10) (2009) 3205–3218. [16] V. R. Rosenfeld, The independence polynomial of rooted products of graphs, Discrete Appl. Math. 158(5) (2010) 551–558. 10 http://dx.doi.org/10.1007/BF02773639 http://dx.doi.org/10.1007/BF02773639 http://dx.doi.org/10.1016/0012-365X(93)E0125-N http://dx.doi.org/10.1016/0012-365X(93)E0125-N http://dx.doi.org/10.1016/j.disc.2010.09.028 http://dx.doi.org/10.1016/j.disc.2010.09.028 http://dx.doi.org/10.1007/s10107-011-0451-5 http://dx.doi.org/10.1007/s10107-011-0451-5 http://dx.doi.org/10.1016/j.disc.2011.11.019 http://dx.doi.org/10.1016/0095-8956(79)90070-4 http://dx.doi.org/10.1002/jgt.3190050203 http://dx.doi.org/10.1002/jgt.3190050203 http://www.ams.org/mathscinet-getitem?mr=724764 http://dx.doi.org/10.1017/S0963548314000613 http://dx.doi.org/10.1017/S0963548314000613 http://dx.doi.org/10.1017/S096354831100068X http://dx.doi.org/10.1017/S096354831100068X http://dx.doi.org/10.1090/memo/1098 http://dx.doi.org/10.1016/j.disc.2008.09.020 http://dx.doi.org/10.1016/j.disc.2008.09.020 http://dx.doi.org/10.1016/j.dam.2009.10.009 http://dx.doi.org/10.1016/j.dam.2009.10.009 Z. Guo et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 1–11 [17] L. Song, W. Staton, B. Wei, Independence polynomials of k−tree related graphs, Discrete Appl. Math. 158(8) (2010) 943–950. [18] M. Trinks, Graph polynomials and their representations, PhD Thesis, Technische Universität Bergakademie Freiberg, 2012. [19] M. Trinks, A survey on recurrence relations for the independence polynomial of hypergraphs, Graphs Combin. 32(5) (2016) 2145–2158. [20] J. A. White, On the multivariate chromatic polynomials of hypergraphs and hyperedge elimination, Electron. J. Combin. 18(1) (2011) P160. [21] F. Zhang, M. Zhou, Matching polynomials of two classes of graphs, Discrete Appl. Math. 20(3) (1988) 253–260. 11 http://dx.doi.org/10.1016/j.dam.2010.01.002 http://dx.doi.org/10.1016/j.dam.2010.01.002 http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-94991 http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-94991 http://dx.doi.org/10.1007/s00373-016-1685-z http://dx.doi.org/10.1007/s00373-016-1685-z http://dx.doi.org/10.1016/0166-218X(88)90081-9 http://dx.doi.org/10.1016/0166-218X(88)90081-9 Introduction The fundamental theorem for matching polynomials Matching polynomials of some special hypergraphs Zeros of matching polynomials of a hypergraphs References