Some New Results On Matching Extension Theory

Matching theory is an important and elementary branch of Graph Theory. Itnot only benefits to understand the structure of graphs but also has widely applica-tions in combinatorial optimization and theoretical chemistry. Matching ExtensionTheory is a popular subject in matching theory. Many valuable results have beenobtained. In particular, some new concepts and new classes of graphs were intro-duced, for example, k-extendable graphs, n-factor-critical graphs, (n,k,d)-graphsand k-cycle resonant graphs, etc. Clearly, the above graphs are useful to furtherstudying the structure of graphs. In the paper, we mainly study the lower boundof removable ears of 1-extendable graphs, extendability of fractional matching ofgraphs, matching extension in odd graphs and excessive index of 1-extendablegraphs.For a graph G, if when deleting any n vertices from G the remaining subgraphof G contains a k-matching and each k-matching of the subgraph can be extendedto a defect-d-matching of the subgraph, then G is called a (n,k,d)-graph. Liuand Yu [1] at the first time introduced the concept which is a generalization ofk-extendable graphs and n-factor-critical graphs. Clearly, each k-extendable graphis (0,k,0)-graph and each n-factor-critical graph is (n,0,0)-graph. In the paper,we also call (0,k,1)-graph is near k-extendable graph. The main contributions ofthe paper are as follows:1. We improve the lower bound of removable ears of 1-extendable graphs whichis obtained by Carvalho, Lucchesi and Murty in [2], and prove each 1-extendablegraph G has at leastχ′(G) edge-disjoint removable ears, whereχ′(G) denotes theedge-chromatic number of G. In addition, we obtain some properties of removableedges of 1-extendable graphs.2. Let G be a 1-extendable graph andχ′_e(G) = min{|M| : M is a set of perfectmatchings of G and M∈M M = E(G)}. We give a tight upper bound ofχ′_e(G).For any positive integer k≥3, we can construct a graph such thatΔ(G) = 3 andχ′_e(G) = k, where k may be enough large. In addition, we consider the excessive index of the Cartesian product of two graphs.3. We improve the characterizations of (n,k,d)-graphs and k-extendablegraphs, characterize near k-extendable graphs and near k-extendable bipartitegraphs, consider the relation of near k-extendable graphs and n-factor-criticalgraphs, and the impact of adding or deleting an edge to near k-extendable graphs.In addition, we also study the matching extension of planar odd graphs.4. We obtain two su?cient conditions of fractional k-extendable graphs, char-acterize minimally fractional k-extendable graphs, and prove that a bipartite graphG is fractional k-extendable if and only if G is k-extendable graph. In addition,we consider the relation of fractional k-extendable graphs and n-factor-criticalgraphs. (For the concept of fractional k-extendable graphs, the reader is referredto Chapter 5)...