Several Results On Near-perfect Matchings And Perfect Matchings In Graphs

Matching theory is a fundamental branch in graph theory, we mainly study the struc-tures of matchings in graphs in this thesis.In the second chapter, we introduced a new concept of vertices in a graph G witha near-perfect matching. Let v be a vertex of a graph G with a near-perfect matching,if every edge incident with v belongs to a near-perfect matching of G, then v is called anear perfect matching totally covered vertex. By using the Gallai-Edmonds structuretheorem in matching theory, a sufcient and necessary condition for a vertex to be a near perfect matching totally covered vertex was obtained. As a byproduct, a characterizationof graphs was given whose vertices were all near-perfect matching totally covered vertices.In the third chapter, two types of graphs with perfect matchings were introduced. LetG be a connected graph with a perfect matching. Then G is said to be vertex contractibleif for any subset S V (G) with|S|is odd, the graph G/S, obtained from G by contractingS to a single vertex, has a perfect matching. The graph G is said to be edge contractibleif for any contraction G′of G with|V (G′)|is even, G′has a perfect matching. By usingTutte,s1-factor Theorem, we gave two characterizations for vertex contractible graphs andedge contractible graphs, respectively. A recursive construction of vertex contractible graphswas also established.