On the matching polynomial of hypergraphs
Keywords:
Hypergraph, Matching polynomial, Line-graph, Independence polynomialAbstract
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.
Downloads
References
N. Alon, J. Kim, and J. Spencer, Nearly perfect matchings in regular simple hypergraphs, Israel J. Math. 100(1) (1997) 171–187.
A. Bretto, Hypergraph Theory: An Introduction, Mathematical Engineering, Springer, Cham, 2013.
R. A. Beezer and E. J. Farrell, The matching polynomial of a regular graph, Discrete Math. 137(1–3) (1995) 7–18.
H. Bian, F. Zhang, G. Wang, and H. Yu, Matching polynomials for chains of cycles, Discrete Math. 311(4) (2011) 319–323.
Y. H. Chan and L. C. Lau, On linear and semidefinite programming relaxations for hypergraph matching, Math. Program. Ser. A 135(1) (2012) 123–148.
F. M. Dong, A new expression for matching polynomials, Discrete Math. 312(4) (2012) 803–807.
E. J. Farrell, An introduction to matching polynomials, J. Combin. Theory Ser. B 27(1) (1979) 75–86.
C. D. Godsil, Algebraic Combinatorics, Chapman and Hall Mathematics Series, Chapman and Hall, New York, London, 1993.
C. D. Godsil and I. Gutman, On the theory of the matching polynomial, J. Graph Theory 5(2) (1981) 137–145.
I. Gutman and F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97–106.
J. Han, Near perfect matchings in $k$–uniform hypergraphs, Combin. Probab. Comput. 24(5) (2015) 723–732.
H. Huang, P. S. Loh, and B. Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21(3) (2012) 442–450.
P. Keevash and R. Mycroft, A geometric theory for hypergraph matching, Mem. Amer. Math. Soc., vol. 233, no. 1098, American Mathematical Society, Providence, RI, 2014.
V. E. Levit and E. Mandrescu, The independence polynomial of a graph–a survey, in: S. Bozapalidis, A. Kalampakas, and G. Rahonis (Eds.), Proceedings of the 1st International Conference on Algebraic Informatics (CAI 2005), Aristotle University of Thessaloniki, 2005, pp. 233–254.
J. P. McSorley and 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, and B. Wei, Independence polynomials of $k$–tree related graphs, Discrete Appl. Math. 158(8) (2010) 943–950.
M. Trinks, Graph polynomials and their representations, Ph.D. 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 multivariate chromatic polynomials of hypergraphs and hyperedge elimination, Electron. J. Combin. 18(1) (2011) #P160.
F. Zhang and M. Zhou, Matching polynomials of two classes of graphs, Discrete Appl. Math. 20(3) (1988) 253–260.
