Some Topics On The Matching Preclusion Number Of Networks

The society is in the era of big data with rapid development,it is urgent to develop and design computer systems with higher fault tolerance,stronger security and more reliability.The reliability and fault tolerance of a computer system depend on the performance of its interconnection network largely.The graph is a natural model of the interconnection network,and many of its parameters are used to measure the level of fault tolerance of network,among which the matching preclusion number can well reflect the ability of the interconnection network operating normally when a link error occurs.When an interconnection network fails,the more likely it is that its topology structure contains a perfect matching or an almost perfect matching,and the matching preclusion number is greater,the level of fault tolerance of network is higher.Therefore,the research on the matching preclusion number of a graph has practical significance and theoretical value on constructing the high-performance massively parallel computer systems.The matching preclusion number of a graph and related issues have been received widespread attention,the matching preclusion number of a graph?a network?has been extensively studied at present.This thesis investigates the matching preclusion number,the conditional matching preclusion number,the strong matching preclusion number,the fractional matching preclusion number,and the relation between them and the structure of a graph.The main results are as follows:?1?Several bounds on the matching preclusion number of a graph are obtained,these bounds are proved to be tight,and the odd and even graphs with given matching preclusion number are characterized respectively.Next,the extremal problem on matching preclusion number is investigated,the results of three extremal parameters related to matching preclusion number s?n,k?,g?n,k?,f?n,k?are obtained,the value of s?n,k?is determined as n=0,1,2,3 and the corresponding extremal graphs are characterized,the result of simulation experiment on the upper bound and lower bound of s?n,k?as n=7,9 is obtained.In the end of this part,the Nordhaus-Gaddum-type results on the matching preclusion number are given and the bounds are proved to be tight.?2?Several bounds on the fractional matching preclusion number of a graph are obtained,these bounds are proved to be tight,and the odd and even graphs with small and large fractional matching preclusion number are characterized respectively.Moreover,the extremal problem on the fractional matching preclusion number is investigated,the results of three extremal parameters related to the fractional matching preclusion number s?n,k?,g?n,k?,f?n,k?are obtained,the value of s?n,k?is determined as n=0,1,2 and the corresponding extremal graphs are characterized,the result of simulation experiment on the upper bound and lower bound of s?n,k?as n=15,17 is obtained.?3?The result on the matching preclusion and conditional matching preclusion of Hierarchical cube networkHCN_nis obtained.First,its matching preclusion number is obtained,and all optimal matching preclusion sets are proved to be trivial.Next,its conditional matching preclusion number is obtained,and all optimal conditional matching preclusion sets are proved to be trivial.?4?The strong matching preclusion number of Augmented butterfly network is investigated.Its strong matching preclusion number is obtained,and all optimal strong matching preclusion sets of it are classified.?5?The fractional matching preclusion number and fractional strong matching preclusion number of the Folded Petersen Cubic Network are investigated.First,its fractional matching preclusion number and the fractional strong matching preclusion number are obtained.Next,all its optimal fractional matching preclusion sets and fractional strong matching preclusion sets are proved to trivial.In the end,an optimization algorithm in order to finding all optimal fractional strong matching preclusion sets containing at least one vertex of low-dimensional Folded Petersen cube network P?Q₁ is showed.