Research On Matching Preclusion And Fractional Matching Preclusion For Graphs

Let G be a graph and F be an edge subset of G.F is called a matching preclusion set of G if G-F has no perfect matching or almost perfect matching.The matching preclusion set with minimum cardinality is called an optimal match-ing preclusion set,and its cardinality is called the matching preclusion number of G,denoted by mp(G).The matching preclusion number was first introduced by Brigham et al.for measuring the robustness of interconnection networks under the condition of edge failure.Furthermore,Cheng et al.introduced the con-cept of conditional matching preclusion.A matching preclusion set F is called a conditional matching preclusion set of G if G-F has no isolated vertex.The conditional matching preclusion set with minimum cardinality is called an optimal conditional matching preclusion set,and its cardinality is called the conditional matching preclusion number of G,denoted by mp1(G).If G has an even number of vertices,we say that the set consisting of edges incident to a single vertex is a trivial matching preclusion set.Moreover,mp(G)is not more than the minimum degree of G,?(G).For a graph G with even order,we say G is maximally matched,if mp(G)= ?(G).Furthermore,if G is maximally matched and every optimal matching preclusion set of G is trivial,then we say G is super matched.Matching preclusion numbers and conditional matching preclusion numbers of many special graphs have been computed,and their optimal matching preclu-sion sets and conditional matching preclusion sets also have been completely char-acterized,such as hypercube,k-ary n-cube,augmented cube,most of these graphs are regular and are proved to be maximally matched and super matched.In this thesis we will first study matching preclusion and conditional matching preclusion for undirected binary de Brujin graph,which is a kind of irregular graph.Then we generally study matching preclusion for regular graph and obtain sufficient and necessary conditions for a regular graph to be maximally matched and super matched,respectively,which improve the sufficient conditions given by Cheng et al.Furthermore,by these results we study the super matched properties of Carte-sian product,direct product and strong product of regular graphs,and the results on Cartesian product can uniformly prove many known results.Especially,we apply linear programming in matching preclusion and introduce the concept of fractional matching preclusion number.This thesis contains five chapters.In chapter 1,first we introduce some useful concepts,terminologies and notations.Then we introduce the research background and development of matching preclusion problem.Finally,we list the main results of this thesis.In chapter 2,we study matching preclusion and conditional matching preclu-sion for undirected binary de Brujin graph UB(n).First we study conditional edge-fault Hamiltonicity of binary de Bruijn graph.Then by this result we show that if n ? 4,then mp(UB(n))= 2 and mp1(UB(n))= 3,and classify all optimal matching preclusion sets and optimal conditional matching preclusion sets.In chapter 3,we characterize maximally matched and super matched regular graph,respectively.Let G be a regular graph with even order.Then we obtain the following results:G is maximally matched if and only if each non-trivial odd cut of G has at least r edges;if G is bipartite,then G is super matched if and only if each non-trivial odd cut of G has at least ? + 1 edges;if G is non-bipartite,then G is super matched if and only if each non-trivial odd cut of G has at least? + 1 edges and independence number of G is less than 1/2|V(G)|-1.In chapter 4,we obtain sufficient conditions for three kinds of products of regular graphs being super matched as follows:Let G and H be two connected regular graphs with more than two vertices.If G or H is maximally matched,then their Cartesian product G?H,direct product G x H and strong product G(?)H are super matched;if G is maximally matched,then G ? K2 is,super matched;if G is super edge-connected and independence number of G is less than 1/2|V(G)|-1,then G x K2 is super matched;if the edge-connectivity of G is equal to ?(G),then G(?)K2 is super matched.Among them,the results on Cartesian product can solve matching preclusion problems of a series of some special graphs uniformly.In chapter 5,we give an integer linear programming to solve mp(G)for a graph G with even order,then by relaxing its integer constraints we introduce fractional matching preclusion number mpf(G).First we show fractional matching preclusion number of graphs can be computed in polynomial time,then an explict formula for fractional matching preclusion number of a bipartite graph is obtained,which helps us find its combinatorial interpretation,that is,k =[mpf(G)]is the maximum integer such that G has k-factor.Finally,we show that if G and H are two bipartite graphs,then mpf(G?H)?mpf(G)+[mpf(H)].