Year 2017, Volume 4 , Issue 1, Pages 1 - 11 2017-01-11

On the matching polynomial of hypergraphs

Zhiwei GUO [1] , Haixing ZHAO [2] , Yaping MAO [3]


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.
Hypergraph, Matching polynomial, Line-graph, Independence polynomial
  • [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.
Subjects Engineering
Journal Section Articles
Authors

Author: Zhiwei GUO

Author: Haixing ZHAO

Author: Yaping MAO

Dates

Publication Date : January 11, 2017

Bibtex @research article { jacodesmath284540, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2017}, volume = {4}, pages = {1 - 11}, doi = {10.13069/jacodesmath.24447}, title = {On the matching polynomial of hypergraphs}, key = {cite}, author = {Guo, Zhiwei and Zhao, Haixing and Mao, Yaping} }
APA Guo, Z , Zhao, H , Mao, Y . (2017). On the matching polynomial of hypergraphs . Journal of Algebra Combinatorics Discrete Structures and Applications , 4 (1) , 1-11 . DOI: 10.13069/jacodesmath.24447
MLA Guo, Z , Zhao, H , Mao, Y . "On the matching polynomial of hypergraphs" . Journal of Algebra Combinatorics Discrete Structures and Applications 4 (2017 ): 1-11 <https://dergipark.org.tr/en/pub/jacodesmath/issue/27044/284540>
Chicago Guo, Z , Zhao, H , Mao, Y . "On the matching polynomial of hypergraphs". Journal of Algebra Combinatorics Discrete Structures and Applications 4 (2017 ): 1-11
RIS TY - JOUR T1 - On the matching polynomial of hypergraphs AU - Zhiwei Guo , Haixing Zhao , Yaping Mao Y1 - 2017 PY - 2017 N1 - doi: 10.13069/jacodesmath.24447 DO - 10.13069/jacodesmath.24447 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 1 EP - 11 VL - 4 IS - 1 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.24447 UR - https://doi.org/10.13069/jacodesmath.24447 Y2 - 2020 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications On the matching polynomial of hypergraphs %A Zhiwei Guo , Haixing Zhao , Yaping Mao %T On the matching polynomial of hypergraphs %D 2017 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 4 %N 1 %R doi: 10.13069/jacodesmath.24447 %U 10.13069/jacodesmath.24447
ISNAD Guo, Zhiwei , Zhao, Haixing , Mao, Yaping . "On the matching polynomial of hypergraphs". Journal of Algebra Combinatorics Discrete Structures and Applications 4 / 1 (January 2017): 1-11 . https://doi.org/10.13069/jacodesmath.24447
AMA Guo Z , Zhao H , Mao Y . On the matching polynomial of hypergraphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2017; 4(1): 1-11.
Vancouver Guo Z , Zhao H , Mao Y . On the matching polynomial of hypergraphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2017; 4(1): 1-11.