g/file/11-7403143x118.png" /> (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. [7] Let G be a connected graph and. Then

where is neighbor vertex set of u in graph G.

Lemma 3.2. 1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12),

13)

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

. Then.

Now, by using mathematical induction to prove (13). Firstly, By (8) and,

(13) holds for. If,

Hence (13) holds for. □

Lemma 3.3. 1)

2)

3)

4)

5)

6)

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)

3) 4)

5) 6)

7) 8)

9) 10)

11) 12).

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

(1)

where and.

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:

(2)

where, and.

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

(3)

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

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

Acknowledgements

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

Cite this paper
Ma, H. and Li, Y. (2016) The Matching Equivalence Graphs with the Maximum Matching Root Less than or Equal to 2. Applied Mathematics, 7, 920-926. doi: 10.4236/am.2016.79082.
References

[1]   Farrell, E.J. (1979) An Introduction to Matching Polynomial. Journal of Combinatorial Theory, 27, 75-86.
http://dx.doi.org/10.1016/0095-8956(79)90070-4

[2]   Godsil, C.D. and Gutman, I. (1981) On the Theory of the Matching Polynomials. Journal of Graph Theory, 5, 79-87.
http://dx.doi.org/10.1002/jgt.3190050203

[3]   Beezer, R.A. and Farrell, E.J. (1995) The Matching Polynomials of a Regular Graph. Discrete Mathematics, 137, 7-8.
http://dx.doi.org/10.1016/0012-365X(93)E0125-N

[4]   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.
http://dx.doi.org/10.1155/S016117129200098X

[5]   Farrell, E.J. and Guo, J.M. (1993) On the Characterizing Properties of Matching Polynomials. Vishwa International Journal of Graph Theory, 2, 55-62.

[6]   Farrell, E.J., Guo, J.M. and Constantine, G.M. (1991) On Matching Coefficents. Discrete Mathematics, 89, 203-210.
http://dx.doi.org/10.1016/0012-365X(91)90369-D

[7]   Godsil, C.D. (1993) Algebraic Combinatorics. Chapman and Hall, New York.

[8]   Godsil, C.D. (1981) Hermite Polynomiala and a Duality Relation for Matching Polynomials. Combinnatorica, 1, 257- 262.
http://dx.doi.org/10.1007/BF02579331

[9]   Godsil, C.D. and Gutman, I. (1981) Some Remarks on the Matching Polynomial and Its Zeros. Croatica Chemica Acta, 54, 53-59.

[10]   Heilmann, O.J. and Lieb, E.H. (1972) Theory of Monomer-Dimer Systems. Communications in Mathematical Physics, 25, 190-232.
http://dx.doi.org/10.1007/BF01877590

[11]   Ma, H.C. and Xia, H. (2001) The Graph with Matching Polynomials Maximum Roots of no Excess 2. Journal of Jilin Institute of Chemical Technology, 18, 67-68. (In Chinese)

[12]   Ma, H.C. (2000) On the Matching Equivalent Classes of Two Kind of Graphs. Journal of Mathematical Study, 33, 218- 222. (In Chinese)

[13]   Ma, H.C. (2002) The Matching Equivalent Classes of Graphs of I Shape. Journal of Mathematical Study, 35, 65-71. (In Chinese)

[14]   Cvetkovic, D.M., Doob, M. and Sachs, H. (1995) Spectra of Graphs. 3rd Edition, Johann Abrosius Barth Verlag.

 
 
Top