On the matching polynomial of hypergraphs

Abstract

The concept of the matching polynomial of a graph, introduced by Farrell in 1979, has received considerable 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 obtained. The exact matching polynomials of some special hypergraphs are given. Further, we discuss the zeros of matching polynomials of hypergraphs.

Keywords

• Hypergraph,Matching polynomial,Line-graph,Independence polynomial

References

1. [1] N. Alon, J. Kim, J. Spencer, Nearly perfect matchings in regular simple hypergraphs, J. Isr. J. Math. 100(1) (1997) 171–187.
2. [2] A. Bretto, Hypergraph Theory, Springer, 2013.
3. [3] R. A. Beezer, E. J. Farrell, The matching polynomial of a regular graph, Discrete Math. 137(1–3) (1995) 7–18.
4. [4] H. Bian, F. Zhang, G. Wang, H. Yu, Matching polynomials for chains of cycles, Discrete Math. 311(4) (2011) 319–323.
5. [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. [6] F. M. Dong, A new expression for matching polynomials, Discrete Math. 312(4) (2012) 803–807.
7. [7] E. J. Farrell, A introduction to matching polynomials, J. Combin. Theory Ser. B 27(1) (1979) 75–86.
8. [8] C. D. Godsil, Algebraic Combinatorics, New York. London: Chapman and Hall, 1993.

9. [9] C. D. Godsil, I. Gutman, On the theory of the matching polynomial, J. Graph Theory 5(2) (1981) 137–145.
10. [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. Rahonis), 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.
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.