All Title Author
Keywords Abstract

Constructing Matching Equivalent Graphs

DOI: 10.4236/am.2017.84038, PP. 476-482

Keywords: Matching Polynomial, Matching Equivalent, Cospectral

Full-Text   Cite this paper   Add to My Lib


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