zbMATH — the first resource for mathematics

Graphs with integer matching polynomial zeros. (English) Zbl 1361.05066
Summary: In this paper, we study graphs whose matching polynomials have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We characterize all matching integral traceable graphs. We show that apart from \(K_7 \setminus(E(C_3) \cup E(C_4))\) there is no connected \(k\)-regular matching integral graph if \(k \geq 2\). It is also shown that if \(G\) is a graph with a perfect matching, then its matching polynomial has a zero in the interval \((0, 1]\). Finally, we describe all claw-free matching integral graphs.

05C31 Graph polynomials
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] Akiyama, J.; Kano, M., Factors and factorizations of graphs: proof techniques in factor theory, vol. 2031, (2011), Springer
[2] Balińska, K.; Cvetković, D.; Radosavljević, Z.; Simić, S.; Stevanović, D., A survey on integral graphs, publikacije elektrotehničkog fakulteta, Ser. Mat., 42-65, (2002) · Zbl 1051.05057
[3] Bondy, J.; Murty, U., (Graph Theory, Graduate Texts in Mathematics, (2008)) · Zbl 1134.05001
[4] Chvátal, V.; Erdös, P., A note on Hamiltonian circuits, Discrete Math., 2, 2, 111-113, (1972) · Zbl 0233.05123
[5] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 3, 1, 69-81, (1952) · Zbl 0047.17001
[6] Godsil, C., Algebraic combinatorics, vol. 6, (1993), CRC Press
[7] Godsil, C. D.; Gutman, I., On the theory of the matching polynomial, J. Graph Theory, 5, 2, 137-144, (1981) · Zbl 0462.05051
[8] Gutman, I., The matching polynomial, MATCH Commun. Math. Comput. Chem., 6, 75-91, (1979) · Zbl 0436.05053
[9] Gutman, I., Characteristic and matching polynomials of some compound graphs, Publ. Inst. Math. (Beograd), 27, 41, 61-66, (1980) · Zbl 0461.05048
[10] Gutman, I., Uniqueness of the matching polynomial, MATCH Commun. Math. Comput. Chem., 55, 351-358, (2006) · Zbl 1110.05083
[11] Gutman, I.; Harary, F., Generalizations of the matching polynomial, Util. Math., 24, 1, 97-106, (1983) · Zbl 0527.05055
[12] Harary, F.; Schwenk, A. J., Which graphs have integral spectra?, (Graphs and Combinatorics, (1974), Springer), 45-51
[13] Heilmann, O. J.; Lieb, E. H., Theory of monomer-dimer systems, (Statistical Mechanics, (1972), Springer), 45-87 · Zbl 0238.05114
[14] Las Vergnas, M., A note on matchings in graphs, Cah. Cent. Etud. Rech. Opér., 17, 2-3, (1975) · Zbl 0315.05123
[15] Sumner, D. P., 1-factors and antifactor sets, J. Lond. Math. Soc., 2, 2, 351-359, (1976) · Zbl 0338.05118
[16] L. Wang, Integral trees and integral graphs, University of Twente, 2005.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.