Araştırma Makalesi
BibTex RIS Kaynak Göster

On the matching polynomial of hypergraphs

Yıl 2017, Cilt: 4 Sayı: 1, 1 - 11, 11.01.2017

Zhiwei Guo Haixing Zhao Yaping Mao

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

Öz

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.

Anahtar Kelimeler

Hypergraph Matching polynomial Line-graph Independence polynomial

Kaynakça

  • [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.

Yıl 2017, Cilt: 4 Sayı: 1, 1 - 11, 11.01.2017

Zhiwei Guo Haixing Zhao Yaping Mao

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

Öz

Kaynakça

  • [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.
Toplam 21 adet kaynakça vardır.

Ayrıntılar

Konular Mühendislik
Bölüm Makaleler
Yazarlar

Zhiwei Guo Bu kişi benim

Haixing Zhao Bu kişi benim

Yaping Mao Bu kişi benim

Yayımlanma Tarihi 11 Ocak 2017
Yayımlandığı Sayı Yıl 2017 Cilt: 4 Sayı: 1

Kaynak Göster

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. Ocak 2017;4(1):1-11. doi:10.13069/jacodesmath.24447
Chicago Guo, Zhiwei, Haixing Zhao, ve Yaping Mao. “On the matching polynomial of hypergraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 4, sy. 1 (Ocak 2017): 1-11. https://doi.org/10.13069/jacodesmath.24447.
EndNote Guo Z, Zhao H, Mao Y (01 Ocak 2017) On the matching polynomial of hypergraphs. Journal of Algebra Combinatorics Discrete Structures and Applications 4 1 1–11.
IEEE Z. Guo, H. Zhao, ve Y. Mao, “On the matching polynomial of hypergraphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 4, sy. 1, ss. 1–11, 2017, doi: 10.13069/jacodesmath.24447.
ISNAD Guo, Zhiwei vd. “On the matching polynomial of hypergraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 4/1 (Ocak2017), 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 vd. “On the matching polynomial of hypergraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 4, sy. 1, 2017, ss. 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.