On the matching polynomial of hypergraphs

Year 2017, Volume: 4 Issue: 1, 1 - 11, 11.01.2017

Zhiwei Guo Haixing Zhao Yaping Mao

https://doi.org/10.13069/jacodesmath.24447

https://izlik.org/JA26ZK54TD

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] 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.
• J. Han, Near perfect matchings in k􀀀uniform hypergraphs, Comb. Probab. Comp. 24(5) (2015) 723–732.
• H. Huang, P. S. Loh, B. Sudakov, The size of a hypergraph and its matching number, Comb. Probab. Comp. 21(3) (2012) 442–450.
• P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, Mem. Amer. Math. Soc. 2015.
• 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.
• J. P. Mcsorley, P. Feinsilver, Multivariate matching polynomials of cyclically labelled graphs, Discrete Math. 309(10) (2009) 3205–3218.
• V. R. Rosenfeld, The independence polynomial of rooted products of graphs, Discrete Appl. Math. 158(5) (2010) 551–558.
• L. Song, W. Staton, B. Wei, Independence polynomials of k􀀀tree related graphs, Discrete Appl. Math. 158(8) (2010) 943–950.
• M. Trinks, Graph polynomials and their representations, PhD Thesis, Technische Universität Bergakademie Freiberg, 2012.
• M. Trinks, A survey on recurrence relations for the independence polynomial of hypergraphs, Graphs Combin. 32(5) (2016) 2145–2158.
• J. A. White, On the multivariate chromatic polynomials of hypergraphs and hyperedge elimination, Electron. J. Combin. 18(1) (2011) P160.
• F. Zhang, M. Zhou, Matching polynomials of two classes of graphs, Discrete Appl. Math. 20(3) (1988) 253–260.