Research ArticleOpen AccessGoogle Scholar indexed
Constructing Matching Equivalent Graphs
School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
School of Mathematics Science, University of Electronic Science and Technology of China, Chengdu, China
- 1 School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
- 2 School of Mathematics Science, University of Electronic Science and Technology of China, Chengdu, China
Copy link · social · email
Abstract
Two nonisomorphic graphs G and H are said to be matching equivalent if and only if G and H have the same matching polynomials. In this paper, some families matching equivalent graphs are constructed. In particular, a new method to construct cospectral forests is given.
KeywordsMatching PolynomialMatching EquivalentCospectral
- Cvetkovic, D.M., Doob, M., Gutman, I. and Torgasev, A. (1988) Recent Results in the Theory of Graph Spectra. North-Holland, Amsterdam.
- Farrell, E.J. (1979) An Introduction to Matching Polynomials. Journal of Combinatorial Theory, Series B, 27, 75-86.
- Liu, W., Guo, Q., Zhang, Y., Feng, L. and Gutman, I. (2017) Further Results on the Largest Matching Root of Unicyclic Graphs. Discrete Applied Mathematics, 221, 82-88.
- Gutman, I. and Wagner, S. (2012) The Matching Energy of a Graph. Discrete Applied Mathematics, 160, 2177-2187.
- Ku, C. and Chen, W. (2010) An Analogue of the Gallai-Edmonds Structure Theorem for Non-Zero Roots of the Matching Polynomial. Journal of Combinatorial Theory, Series B, 100, 119-127.
- Lass, B. (2004) Matching Polynomials and Duality. Combinatorica, 24, 427-440. https://doi.org/10.1007/s00493-004-0026-7
- Li, X., Shi, Y. and Trinks, M. (2015) Polynomial Reconstruction of the Matching Polynomial. Electronic Journal of Graph Theory and Application, 3, 27-34. https://doi.org/10.5614/ejgta.2015.3.1.4
- Wu, T., Yan, W. and Zhang, H. (2016) Extremal Matching Energy of Complements of Trees. Discussiones Mathematicae Graph Theory, 36, 505-522. https://doi.org/10.7151/dmgt.1869
- Wu, T. (2016) Two Classes of Topological Indices of Phenylene Molecule Graphs. Mathematical Problems in Engineering, 2016, Article ID: 8421396. https://doi.org/10.1155/2016/8421396
- Yan, W., Yeh, Y. and Zhang, F. (2005) On the Matching Polynomials of Graphs with Small Number of Cycles of Even Length. International Journal of Quantum Chemistry, 105, 124-130. https://doi.org/10.1002/qua.20670
- Yan, W. and Yeh, Y. (2009) On the Matching Polynomial of Subdivision Graphs. Discrete Applied Mathematics, 157, 196-200.
- Zhang, H., Lin, R. and Yu, G. (2013) The Largest Matching Root of Unicyclic Graphs. Information Processing Letters, 113, 804-806.
- Zhang, H., Yu, G. and Li, S. (2015) Graphs with Six Distinct Matching Roots. Information Processing Letters, 115, 521-526.
- Gutman, I. (2016) A Survey on the Matching Polynomial. In: Shi, Y., et al., Eds., Graph Polynomial, CRC Press, Boca Raton.
- Godsil, C.D. and Gutman, I. (1981) On the Theory of the Matching Polynomial. Journal of Graph Theory, 5, 137-144. https://doi.org/10.1002/jgt.3190050203