Some Topics On The Matching Preclusion Set Of Graphs

In recent years,many networks have been proposed as the topology of large-scale parallel distributed systems.Because of the link and node failures when the network is put into use,it is very important to consider the network with fault components.The concept of strong matching preclusion number of graph G was proposed by Park and Ihm.Let F' be a subset of edges and vertices of a graph G.If G-F' has neither perfect matching nor almost perfect matching,then the minimum number of edges and vertices of F' is called strong matching preclusion number.Graph G is strongly super matched if every optimal strong matching preclusion set is trivial.Yan Liu and others put forward the concepts of fractional matching preclusion number and fractional strong matching preclusion number.Let F be an edge subset of a graph G.If G-F has no fractional perfect matching,then the minimum number of edges of F is called fractional matching preclusion number(FMP number).Graph G is fractional super matched if every optimal fractional matching preclusion set is trivial.Let F' be a subset of edges and vertices of a graph G.If G-F' has no fractional perfect matching,then minimum number of F' is called fractional strong matching preclusion number(FSMP number).Graph G is fractional strongly super matched if every optimal fractional strong matching preclusion set is trivial.The induction and counter evidence methods are mainly used in this thesis.We s-tudy FMP number,FSMP number and properties of fractional(strong)super matching of split-star networks.The strong matching preclusion number,properties of strong su-per matching,FMP number,FSMP number and properties of fractional(strong)super matching of binary de Bruijn graphs are also studied.Furthermore,the Hamiltonian connectivity,essentially matchable and properties of strong super matching of data center network,and the FMP number and properties of fractional super matching of four kinds of graph products are also studied.