Applied Mathematics
Vol.08 No.04(2017), Article ID:75586,7 pages
10.4236/am.2017.84038
Constructing Matching Equivalent Graphs
Tingzeng Wu1, Huazhong Lü2
1School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
2School of Mathematics Science, University of Electronic Science and Technology of China, Chengdu, China
Copyright © 2017 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: March 28, 2017; Accepted: April 21, 2017; Published: April 24, 2017
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.
Keywords:
Matching Polynomial, Matching Equivalent, Cospectral
1. Introduction
We use standard graph-theoretical notation and terminology. For concepts and notations not defined here, we refer the reader to [1] .
By a graph we always mean a simple undirected graph G with the vertex set and the edge set .We denote the complement of G by . The degree of a vertex is denoted by , abbreviated as . Let be the union of two graphs G and H which have no common vertices. For any positive integer l, let lG be the union of l disjoint copies of graph G. An acyclic graph, containing no cycles, is called a forest. A connected forest is called a tree. The complete bipartite graph with vertices is denoted by . The path, star and complete graph with vertices are denoted by , and , respectively.
A r-matching in G is a set of r pairwise non-incident edges. The number of r- matchings in G is denoted by . Specifically, and
for . It is both consistent and convenient to define . The matching polynomial of the graph G is defined as
(1)
Matching polynomials have some important applications in statistical physics and structural chemistry. Up to now, the matching polynomials of graphs are extensively examined, we refer the reader to [2] - [14] and the references therein.
Two nonisomorphic graphs G and H are said to be matching equivalent, symbolically , if . Godsil and Gutman [15] first proposed the question to determine matching equivalent graphs. This seems difficult in the theory of graph polynomials. By now, little about the matching equivalent graphs have been published [16] [17] [18] [19] . In this paper, we plan to investigate the problem which graphs are matching equivalent.
2. Some Lemmas
In the section, we will present some lemmas which are required in the proof of the main results.
Lemma 1. [19] [20]
(2)
Corollary 1. if and only if .
Proof. Corollary 1 follows directly by Lemma 1.
Lemma 2. [19] The matching polynomial satisfies the following identities:
1) ;
2) if is an edge of G;
3) , if .
Let G be a graph with a vertex u. The path tree is the tree with the paths in G which start at u as its vertices, and where two such paths are joined by an edge if one is a maximal subpath of the other.
Lemma 3. [21] Suppose G is a connected graph with , and suppose is the path tree associated with G with root u. Then has a subforest such that
(3)
Remark 1. It is not difficult to derive the following description of an appropriate subforest : find a spanning tree of G by depth-first search from u, and delete from T all vertices corresponding to a path contained in .
Wu and Zhang [22] determined all connected graphs with matching number 2 as follows.
Lemma 4. ( [22] ) Let G be a connected graph with n vertices. Then if and only if G is one of 22 graphs as shown in Figure 1, where in , in , in , in , in , and in , and and in , and and in .
The eigenvalues of the adjacency matrix of G, denoted by are the eigenvalues of G, and form the spectrum of G [1] . Two nonisomorphic
Figure 1. All connected graphs with the matching number 2.
graphs of the same order are cospectral if they have the same spectrum.
Lemma 5. ( [19] ) If G is a forest then , where denotes the characteristic polynomial of G.
Lemma 5 implies the following result.
Corollary 2. Let G and H be two forests. If , then G and H are cospectral.
3. Main Results
For convenience, and in Figure 1 are replaced by and , respectively, where and denote the degree of vertices u and v, respectively, and k denotes the number of common neighbors of u and v.
Theorem 1. .
Proof. By (2) of Lemma 2, we have
and
Thus, .
By Corollary 1 and Theorem 1, we have
Corollary 3. .
Theorem 2. and are matching equivalent, and their complements are also matching equivalent, where .
Proof. By (2) of Lemma 2, we have
and
Checking and , it can be seen that and are isomorphic. So, . By Corollary 1, .
Theorem 3. Let G be a graph obtained by identifying a cycle to vertex u of , and let H be a graph obtained by attaching a path to a vertex of degree two in , where (see Figure 2). Then and .
Proof. By (2) of Lemma 2, we obtain that and . Checking G and H, it can be known that and are isomorphic. So, . By Corollary 1, again we have .
Checking , it is easy to find that and are matching equivalent. Based on the result above, we construct a pair of matching equivalent graphs as follows.
Theorem 4. Let G be a graph obtained by joining two single vertices to in , and let H be a graph obtained by joining a single vertex to and in , respectively, where and are both in the bipartition of q vertices in (see Figure 3). Then and .
Proof. By (2) of Lemma 2, we obtain that and . Checking G and H, it can be known that and are isomorphic. So, . By Corollary 1, we have .
Figure 2. Graphs G and H in Theorem 3.
Figure 3. Graphs G and H in Theorem 4.
Theorem 5. Let G be a graph obtained by attaching a path to in , and let H be a graph obtained by identifying the center of to a pendant vertex of (see Figure 4). Then and .
Proof. By (2) of Lemma 2, we obtain that and . Checking G and H, it can be known that is isomorphic to . So . By Corollary 1, we have .
Theorem 6. Let G and H be two graphs which are defined in Theorem 5. Then and , where I denotes a graph obtained by attaching a single vertex to a pendant vertex of , and and denote the path-trees of G and H, respec- tively (see Figure 5). In particular, and are cospec- tral.
Proof. By Lemma 3, we have and . By Theorem 5, we have . So, . This implies that .
By Corollary 1, we have . Furthermore, by Corollary 5, we know that and are cospectral.
4. Conclusion
In this paper, we constructed some families matching equivalent graphs in Theorems 1,..., and 4. Based on these results, using the same method in Theorem 6, we can construct some pairs of matching equivalent forests and cospectral forests, respectively.
Figure 4. Graphs G and H in Theorem 5.
Figure 5. Path trees of G and H in Theorem 6.
Acknowledgements
We thank the editor and referees for their comments. Research of Tingzeng Wu is funded by NSF of Qinghai (2016-ZJ-947Q), and high-level personnel of scientific research projects of QHMU(2016XJG07). These supports are greatly appreciated.
Cite this paper
Wu, T.Z. and Lü, H.Z. (2017) Constructing Matching Equivalent Graphs. Applied Mathematics, 8, 476- 482. https://doi.org/10.4236/am.2017.84038
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-Equivalence 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.