﻿ The Matching Uniqueness of A Graphs

Applied Mathematics
Vol.06 No.08(2015), Article ID:57743,3 pages
10.4236/am.2015.68109

The Matching Uniqueness of A Graphs

Shichang Shen

School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China

Email: 13909785766@163.com

Copyright © 2015 by author and Scientific Research Publishing Inc.   Received 20 March 2015; accepted 30 June 2015; published 3 July 2015

ABSTRACT

In the paper, We discussed the matching uniqueness of graphs with degree sequence . The necessary and sufficient conditions for and its complement are matching unique are given.

Keywords:

Graph, Matching Polynomial, Matching Uniqueness 1. Introduction

All graphs considered in the paper are simple and undirected. The terminology not defined here can be found in  . Let G be a graph with n vertices. An r-matching in a graph G is a set of r edges, no two of which have a vertex in common. The number of r-matching in G will be denoted by . We set and define the matching polynomial of G by For any graph G, the roots of are all real numbers. Assume that , the

largest root is referred to as the largest mathing root of G.

Throughout the paper, we denote by and the path and the cycle on n vertices, respectively. denotes the tree with a vertex v of degree 3 such that , and denotes the tree obtained by appending a pendant vertex of the path in to a vertex with degree 2 of . is obtained by appending a cycle to a pendant vertex of a path. Two graphs are matching equivalency if they share the same matching polynomial. A graph G is said to be matching unique if for any graph H, implies that H is isomorphic to G. The study in this ares has made great progress. For details, the reader is referred to the surveys  - . In the paper, we prove

and its complement are matching unique if and only if or

.

2. Basic Results

Lemma 1  The matching polynomial satisfies the following identities:

1).

2) if is an edge of G.

Lemma 2  Let G be a connected graph, and let H be a proper subgraph G.

Then.

Lemma 3  Let, if, then H are precisely the graphs of the following

types:

Lemma 4 1)  .

2)  .

3)  .

4)  ,

.

5)  .

6)  .

Lemma 5  Let G be a tree and let be obtained from G by subdividing the edge uv of G, then

1), if uv not lies on an internal path of G.

2), if uv lies on an internal path of G, and if G is not isomorphic to.

Lemma 6  are matching unique.

Lemma 7.

Proof. Direct computation (using Matlab 8.0), we immediately have the following:

,

.

By Lemma 2, 5, we get

.

3. Main Results

Theorem 1 Let, then G are matching unique if and only if or

.

Proof. The necessary condition follows immediately from Lemma 1. We have

Now suppose that or, H is a graph being matching equivalency with G. We proceed to prove that H must be isomorphic to G. By Lemma 3

Case 1. If. By, we know that. Hence, the component of

in H may be only. By Lemma 4, and

. Let, then, a contradiction. Let. If, then, a contradiction. If, then, a contradic-

tion. If, then, a contradiction. Let. If, then

, a contradiction. If s2 ≥ 2, then,

a contradiction. Let. If, then, a contradiction. If, then

, a contradiction. Let, then

Case 2 If. By, hence the component of in H may be

only. Let. If, then, a contradiction. If, then

, a contradiction. If, then, by Lemma 4, we get, thus. That is,

, then

, by Lemma 6, has at least one equal to 6, a contradiction. If,

by Lemma 4, 6, we have, thus H be isomorphic to G. Let. If,

, a contradiction. If, a contradiction. Let, by

Lemma 4, , a contradiction.

Case 3 If, by, a contradiction. Combing cases 1 - 3, H is isomorphic to G.

The proof is complete. For a graph, its matching polynomial determine the matching polynomial of its Comple-

ment  , so the complement of are matching unique if and only if or.

References

1. Godsil, C.D. (1993) Algebraic Combinatorics. Chapman and Hall, New York, London.
2. Shen, S.C. (2001) A Necessary and Sufficient Conditions for Matching Uniqueness of a Class of T-Shape tree. Journal of Mathematical Study, 34, 411-416.
3. Ma, H.C. (2003) The Matching Equivalent Classes of Graphs with the Maximum Root Less than 2. Journal of Systems Science and Mathematical Sciences, 3, 337-342.
4. Cvetkovic, D.M., Doob, M. and Sachs, H. (1980) Spectra of Graphs. Academic Press, New York.
5. Ghareghani, N., Omidi, G.R. and Tayfeh-Rezaie, B. (2007) Spectral Characterization of Graphs with Index at Most. Linear Algebra and Its Applications, 420, 483-489. http://html.scirp.org/file/2-7402693x122.png" . Linear Algebra and Its Applications, 420, 483-489. http://dx.doi.org/10.1016/j.laa.2006.08.009
6. Beezet, R.A. and Farrell, E.J. (1995) The Matching Polynomials of a Regular Graphs. Discrete Mathematics, 137, 7- 18.