Publish in OALib Journal
ISSN: 2333-9721
APC: Only $99

Paper Submission

Views	Downloads

Relative Articles
THE MATCHING EQUIVALENT CLASSES OF GRAPHS WITH THE MAXIMUM MATCHING ROOT LESS THAN 2 匹配最大根小于2的图的匹配等价类
On The Chromatic Number of Matching Graphs
Graphs with few matching roots
Bipartite graphs with a perfect matching and digraphs
Constructing Geometrically Equivalent Hyperbolic Orbifolds
Complexes of graphs with bounded matching size
Maximum matching on random graphs
The number of conformally equivalent maximal graphs
Matching in Gabriel Graphs
The Matching Uniqueness of A Graphs
More...

Applied Mathematics 2017

Constructing Matching Equivalent Graphs

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

Tingzeng Wu, Huazhong Lü

Keywords: Matching Polynomial, Matching Equivalent, Cospectral

Full-Text Cite this paper Add to My Lib

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.

References

[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. https://doi.org/10.1007/s00493-004-0026-7
[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
[8]	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
[9]	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
[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.

Full-Text