Research Article
BibTex RIS Cite

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

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.

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

Zhiwei Guo Haixing Zhao Yaping Mao

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

Abstract

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.
There are 21 citations in total.

Details

Subjects Engineering
Journal Section Articles
Authors

Zhiwei Guo This is me

Haixing Zhao This is me

Yaping Mao This is me

Publication Date January 11, 2017
Published in Issue Year 2017 Volume: 4 Issue: 1

Cite

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. 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. January 2017;4(1):1-11. doi:10.13069/jacodesmath.24447
Chicago Guo, Zhiwei, Haixing Zhao, and Yaping Mao. “On the Matching Polynomial of Hypergraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 4, no. 1 (January 2017): 1-11. https://doi.org/10.13069/jacodesmath.24447.
EndNote Guo Z, Zhao H, Mao Y (January 1, 2017) On the matching polynomial of hypergraphs. Journal of Algebra Combinatorics Discrete Structures and Applications 4 1 1–11.
IEEE Z. Guo, H. Zhao, and Y. Mao, “On the matching polynomial of hypergraphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 4, no. 1, pp. 1–11, 2017, doi: 10.13069/jacodesmath.24447.
ISNAD Guo, Zhiwei et al. “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.
JAMA Guo Z, Zhao H, Mao Y. On the matching polynomial of hypergraphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2017;4:1–11.
MLA Guo, Zhiwei et al. “On the Matching Polynomial of Hypergraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 4, no. 1, 2017, pp. 1-11, doi:10.13069/jacodesmath.24447.
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.