Matching integral graphs with maximum vertex degree four

Articles in Press

Document Type : Research Paper

Author

Science and Research Branch, Islamic Azad University, Tehran, Iran

10.22108/toc.2025.143470.2225

Abstract

The matching polynomial of a graph has coefficients that give the number of matchings in the graph. In this paper, we determine all connected graphs with maximum vertex degree four whose matching polynomials have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We show that there are exactly two matching integral graphs with maximum vertex degree four.

Keywords

Main Subjects

References

[1] S. Akbari, P. Csikvári, A. Ghafari, S. Khalashi Ghezelahmad and M. Nahvi, Graphs with integer matching polynomial zeros, Discrete Appl. Math., 224 (2017) 1–8.
[2] K. T. Balińska, D. Cvetković, Z. Radosavljević, S. K. Simić and D. Stevanović, A survey on integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 13 (2002) 42–65.
[3] E. J. Farrell, An introduction to matching polynomials, J. Combin. Theory Ser. B, 27 no. 1 (1979) 75–86.
[4] E. Ghorbani, Graphs with few matching roots, Graphs Combin., 29 no. 5 (2013) 1377–1389.
[5] C. D. Godsil, Algebraic Combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993.
[6] C. D. Godsil, Algebraic matching theory, Electron. J. Combin., 2 (1995) 1–14.
[7] C. D. Godsil and I. Gutman, On the theory of the matching polynomial, J. Graph Theory, 5 no. 2 (1981) 137–144.
[8] I. Gutman, The matching polynomial, MATCH Commun. Math. Comput. Chem., no. 6 (1979) 75–91.
[9] I. Gutman, Uniqueness of the matching polynomial, MATCH Commun. Math. Comput. Chem., 55 no. 2 (2006) 351–358.
[10] F. Harary and A. J. Schwenk, Which graphs have integral spectra?, Graphs and Combinatorics, Lecture Notes in Math., Springer-Verlag, Berlin,406 (1974) 45–51.
[11] O. J. Heilmann and E. H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys., 25 (1972) 190–232.
[12] S. Khalashi Ghezelahmad, On matching integral graphs, Math. Sci., 13 (2019) 387–394.
[13] S. Khalashi Ghezelahmad, Matching integral graphs of small order, JNRM, 6 no. 26 (2020) 99–111.
[14] C. Y. Ku and W. Chen, An analogue of the Gallai-Edmond structure theorem for non-zero roots of the matching polynomial, J. Combin. Theory Ser. B, 100 no. 2 (2010) 119–127.
Transactions on Combinatorics

Articles in Press, Corrected Proof
Available Online from 12 November 2025

Files

History

  • Receive Date: 22 November 2024
  • Revise Date: 12 September 2025
  • Accept Date: 22 September 2025
  • Published Online: 12 November 2025

Share

How to cite

Statistics