Received 23 March 2016; accepted 24 May 2016; published 27 May 2016
Let G be a finite simple graph with vertex set and edge set. A spanning subgraph H is called a matching of G, if every connected component of H is isolated edge or isolated vertex. k-matching of G is a matching with k edges. A matching polynomial of G is defined as
where is the number of k-matchings of G.
Two graphs G and H are called matching-equivalent if, and denoted by. A graph G is called matching unique if implies that. The union of two graphs G and H, denoted by, is the graph with vertex set and edge set. denotes the union of k graphs G.
More than 30 years ago E. J. Farrell in  introduced the concept of matching polynomials. Latterly, Godsil and Gutman in  gave another definition. Here we use the definition given by Godsil. Form then on, the research on the properties of matching polynomials has largely been done (see  -  ). But the research on matching-equivalent of graphs is few. In this paper, we give a necessary and sufficient condition of matching equivalence of two graphs with the maximum matching root less than or equal to 2.
Throughout the paper, by and, respectively, denote the path and the cycle with n vertices. denotes the maximum degree of graph G. By denote the star graph with 5 vertices. By denote the tree which has one 3-degree vertex u and three 1-degree vertices and the distance between u and are, respectively. A graph is defined as the graph obtained by identifying one end of the path with a vertex of the cycle. Let be a path with vertices; sequence, denotes the tree obtained by adding pendant edges at vertices 2 and of, respectively. The graphs are shown in Figure 1.
2. Graphs with the Maximum Matching Root Less than or Equal to 2
Let G be a graph with order n. Since the roots of are real numbers (see  ), the maximum root of denoted by, the characteristic polynomial of graph G denoted by and the maximum root of denoted by (is also called spectral radius of graph G), respectively. In this section, we determine graphs with the maximum matching root less than or equal to 2, we firstly give some useful lemmas as follows:
Lemma 2.1.  Let G be a graph with k components. Then
Lemma 2.2.  Let G be a forest. Then.
Lemma 2.3.  Let G be a connected graph and. Then
1) is a single root of and.
2) is a single root of and.
Definition 2.1. Let G be a connected graph with a vertex u. The path-tree is a 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.
Clearly, if G is a tree, then the path tree.
Lemma 2.4.  Let u be a vertex in the graph G and be the path tree of G with respect to u. Then
Lemma 2.5. Let G is a connected graph and. Then is spectral radius of path-tree. i.e.,
Proof. By Lemmas 2.2 and 2.4, we have, by Lemma 2.3, we have and, comparing with the maximum root of and, we can obtain
□Lemma 2.6.  Let T be a tree. Then
1) if and only if,
2) if and only if.
Theorem 2.1. Let G be a connected graph. Then
Figure 1. The graphs and.
1) if and only if.
2) if and only if.
Proof. (1) Since the path-tree of respect to an arbitrary vertex and respect to the 3 degree vertex are and, respectively. By Lemmas 2.5 and 2.6 the sufficiency is obvious.
Case 1. If G is a tree.
Clearly,. By Lemma 2.6,.
Case 2. If G isn’t a tree.
By Lemma 2.5 and 2.6, the path-tree respect to an arbitrary vertex u of G is. Then we get that the maximum degree and the number of 3-degree vertex of G is at most 1 (otherwise,).
Subcase 2.1. If. It is clear that G has only one 3 degree vertex, thus (otherwise, or G is a tree). Clearly, the path-tree of G respect to the 3 degree vertex u is , Since, thus we have, i.e.,.
Subcase 2.2. If.
Since G is connected and isn't a tree, then G is. Thus.
(2) Since the path-tree of and respect to the 3 degree vertex are and, respectively. By Lemmas 2.5 and 2.6 the sufficiency is clear.
Case 1. If G is a tree.
Clearly,. By Lemma 2.6,.
Case 2. If G isn’t a tree.
By Lemma 2.5, the path-tree respect to an arbitrary vertex u of G is, thus. Denote. In order to complete the proof, we will divide four subcases as follows:
Subcase 2.1. If.
Let u is a 4 degree vertex of G. Since, then, and thus.
Subcase 2.2. If and.
It is clear that the number of 3 degree vertex of path-tree respect to an arbitrary vertex u of G is also greater than 2. Hence.
Subcase 2.3. If and, then G is one of the graphs and (see Figure 2) Clearly,.
Subcase 2.4. If and.
It is clear that and the path-tree respect to the 3 degree vertex u is. Since, thus or. i.e., or.
By Theorem 2.1 and Lemma 2.1, we can easily obtain the following Theorem 2.2:
Theorem 2.2. Let G be a graph. Then
1) if and only if every connected component of G belongs to.
2) and 2 is m multiple root of if and only if m connected components of G belong to and others belong to.
Figure 2. Four connected graphs with and.
3. Sufficient and Necessary Condition for Matching Equivalence of Graphs
In this section, the sufficient and necessary condition for matching equivalence of graphs with the maximum matching root less than or equal to 2 is determined. Firstly, we give some lemmas as follows:
Lemma 3.1.  Let G be a connected graph and. Then
where is neighbor vertex set of u in graph G.
Lemma 3.2. 1)
Proof. (1) Let the vertices sequence of path is, by Lemma 3.1, consider with and with any one vertex, thus (1) holds.
(2) Let v be the 3 degree vertex and u be a such pendant vertex of that the distance between u and v is 1. By Lemma 3.1, consider with u and with any one vertex, thus (2) holds.
(3)-(12) The results (3)-(12) can easily obtained by the following equalities.
(13) By Lemma 3.1, and
Now, by using mathematical induction to prove (13). Firstly, By (8) and,
(13) holds for. If,
Hence (13) holds for. □
Lemma 3.3. 1)
Proof. Clearly, by Lemma 2.3, we obtain Lemma 3.3(1) immediately. And comparing with the maximum root of two sides of equalities in Lemma 3.2, other results in Lemma 3.3 is also obvious. □
Definition 3.1. Let G and be graphs, if
where be integers. Then G is called a linear combination of, and denote .
Note that some is allowed to be negative. In fact, if all are positive, then is a graph. And when some is negative for doesn’t stand for a graph. In any case, implies that polynomials and are equal. For example, since, we can denote.
By Lemma 3.2, the following representations are also obvious.
Lemma 3.4. 1) 2)
Lemma 3.5. If. Then G can uniquely be represented as a linear combination of the form
and the non-vanishing coefficient, with the greatest, is positive. Furthermore, if is the longest path with the non-vanishing coefficient,.
Proof. Since, by Theorem 2.2, every connected component of G belongs to. According to Lemma 3.4, we get that G can be represented as a linear combination of paths. Next, without loss of generality, assume that G can be represented as
Now by transposition terms from side to side of Equations (1) to (2) such that the coefficients of and are positive, without loss of generality, Assumes that the Equation (2) as follows:
Compare with the maximum root and its multiplicity of graphs in two sides of (2), we shall get. Thus
Repeat this proceeding, we shall get and for. That is, G can uniquely be represented as a linear combination of paths.
Furthermore, assume that G be represented as a linear combination
and is the non-vanishing coefficient of the longest path in (3). Then.
In fact, assume that, then by transposition terms from side to side of Equation (3) such that the coefficients of are positive, we can obtain Equation (4).
where and. By comparing with the maximum root of and, we can obtain
it is a contradiction. Thus and then modify (4) as
compare with the maximum root of and we can obtain
Lemma 3.6. If, then G can uniquely be represented as a linear combination of the form and equals to the multiplicity of root 2 of.
Proof. Since, by Theorem 2.2, every connected component of G belongs to. According to Lemma 3.4, we easily obtain that G can be represented as a linear combination of and some paths. Next, without loss of generality, assume that G can be represented as
By transposition terms and comparing with the multiplicity of root 2, we have equal to the multiplicity of root 2 of. Thus
Furthermore, we can obtain and for.
By Lemmas 3.5, 3.6 and Definition 3.1 we immediately get. □
Theorem 3.1. Let be graphs. Then
1) If, then if and only if G and H have the same linear combination repre- sentation of paths.
2) If, then if and only if G and H have the same linear combination repre- sentation of and some paths.
This work is supported by National Natural Science Foundation of China (11561056), National Natural Science Foundation of Qinghai Provence (2011-Z-911), and Scientific Research Fund of Qinghai University for Nationalities (2015G02).
 Farrell, E.J. (1979) An Introduction to Matching Polynomial. Journal of Combinatorial Theory, 27, 75-86.
 Godsil, C.D. and Gutman, I. (1981) On the Theory of the Matching Polynomials. Journal of Graph Theory, 5, 79-87.
 Beezer, R.A. and Farrell, E.J. (1995) The Matching Polynomials of a Regular Graph. Discrete Mathematics, 137, 7-8.
 Farrell, E.J. and Whitehead Jr., E.G. (1992) Connections between the Matching and Chromatic Polynomials. International Journal of Mathematics and Mathematical Sciences, 15, 757-766.
 Farrell, E.J., Guo, J.M. and Constantine, G.M. (1991) On Matching Coefficents. Discrete Mathematics, 89, 203-210.
 Godsil, C.D. (1981) Hermite Polynomiala and a Duality Relation for Matching Polynomials. Combinnatorica, 1, 257- 262.
 Heilmann, O.J. and Lieb, E.H. (1972) Theory of Monomer-Dimer Systems. Communications in Mathematical Physics, 25, 190-232.