Constructing Matching Equivalent Graphs
, PP. 476-482 10.4236/am.2017.84038
Keywords: Matching Polynomial, Matching Equivalent, Cospectral
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.
[ 1] Cvetkovic, D.M., Doob, M., Gutman, I. and Torgasev, A. (1988) Recent Results in the Theory of Graph Spectra. North-Holland, Amsterdam.
[ 2] Farrell, E.J. (1979) An Introduction to Matching Polynomials. Journal of Combinatorial Theory, Series B, 27, 75-86.
[ 3] 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.
[ 4] Gutman, I. and Wagner, S. (2012) The Matching Energy of a Graph. Discrete Applied Mathematics, 160, 2177-2187.
[ 5] 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.
[ 6] Lass, B. (2004) Matching Polynomials and Duality. Combinatorica, 24, 427-440.
[ 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.
[ 8] Wu, T., Yan, W. and Zhang, H. (2016) Extremal Matching Energy of Complements of Trees. Discussiones Mathematicae Graph Theory, 36, 505-522.
[ 9] Wu, T. (2016) Two Classes of Topological Indices of Phenylene Molecule Graphs. Mathematical Problems in Engineering, 2016, Article ID: 8421396.
[ 10] 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
[ 11] Yan, W. and Yeh, Y. (2009) On the Matching Polynomial of Subdivision Graphs. Discrete Applied Mathematics, 157, 196-200.
[ 12] Zhang, H., Lin, R. and Yu, G. (2013) The Largest Matching Root of Unicyclic Graphs. Information Processing Letters, 113, 804-806.
[ 13] Zhang, H., Yu, G. and Li, S. (2015) Graphs with Six Distinct Matching Roots. Information Processing Letters, 115, 521-526.
[ 14] Gutman, I. (2016) A Survey on the Matching Polynomial. In: Shi, Y., et al., Eds., Graph Polynomial, CRC Press, Boca Raton.
[ 15] 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
[ 16] Beezer, R.A. and Farrell, E.J. (1995) The Matching Polynomial of a Regular Graph. Discrete Mathematics, 137, 7-18.
[ 17] Ma, H. and Ren, H. (2007) The New Methods for Constructing Matching-Equiva- lence Graphs. Discrete Mathematics, 307, 125-131.
[ 18] Zhang, H. and Shu, J. (2012) On the Matching Polynomial of Theta Graphs. Ars Combinatoria, 104, 477-490.
[ 19] Godsil, C.D. (1993) Algebraic Combinatorics. Chapman & Hall, New York, London.
[ 20] Farrell, E.J. and Whitehead, E.G. (1992) Connections between the Matching and Chromatic Polynomials. International Journal of Mathematics and Mathematical Sciences, 15, 757-766. https://doi.org/10.1155/S016117129200098X
[ 21] Lovász, L. and Plummer, M.D. (2009) Matching Theory. American Mathematical Society.
[ 22] Wu, T. and Zhang, H. (2015) Per-Spectral Characterizations of Graphs with Extremal Per-Nullity. Linear Algebra and Its Applications, 484, 13-26.
comments powered by Disqus. comments powered by