| Matching theory is a basic subject in the graph theory with some important applications in theoretical chemistry and combinatorial optimization. The main focus of matching theory is to investigate the constructions and structual properties of graphs with perfect matchings, such as elementary graphs, n-extendable graphs, k-critical graphs and k-cycle resonant graphs, and enumerate the perfect matchings of graphs. In this paper, we study some graphs with perfect matchings which also have perfect matchings after contracting some vertices, and obtain some upper and lower bounds of the numbers of the perfect matchings of some special types of graphs.Key contributions of this paper are as follows:1. By introducting two types of vertex contractions in a graph, called α2n+1-contraction and β2n-contraction respectively, we introduce two new classes of graphs, called (2n+1)-contractible graphs and 2n-pairs contractible graphs. ( Let G be a graph. For a subset S of V(G) with |S| = 2n+1, α2n+1(G, S) denotes the graph obtained from G by contracting S to a single vertex. If G has a perfect matching and, for any subset S of V(G) with |S| = 2n+ 1, the graph α2n+1(G, S) always has a perfect matching, then G is called a (2n+1)-contractible graph. For pairwise disjoint subsets S1, S2, ···, S2n of V(G), β2n(G, S1, S2,···, S2n) denotes the graph obtained from G by contracting each Si, i = 1, 2, ···, 2n, to a single vertex respectively. If G has a perfect matching and, for any pairwise disjoint subsets S1, S2, ···, S2n of V(G) with |S1|=|S2| = ··· = |S2n| = 2, the graph β2n(G, S1, S2,···, S2n) always has a perfect matching, then G is called a 2n-pairs contractible graph). Some simple necessary and sufficient conditions for a graph to be a (2n + 1)-contractible (resp. a 2n-pairs contractible) graph are established by using the Tutte Theorem. We also investigate the relations between 2n-critical graphs, (2n + 1)-contractible graphs, 2n-pairs contractible graphs, and n-extendable graphs.2. Some novel characterizations of n-extendable bipartite graphs are given based on the α2n+1-contraction and β2n-contraction.3. The tight upper bounds of the numbers of perfect matchings in graphs with some structual properties are determined. We prove that the tight upper bound of the...
|
PDF Full Text Request