Conditional Matching Preclusion For The Modified Bubble Sort Graph

With the development of modern science and technology and the increasing information exchange,people’s requirements for the performance of interconnection network computers are also gradually improved.The most important part of these computer systems is the topology structure between the various processors.In a certain sense,the graph and network topology are equivalent,and then the research on network topology can be transformed into the study of graph structure.In some practical application problems,such as personnel assignment problems,optimal assignment problems and winning strategy in games,we often need to judge whether these problems have a perfect matching or an almost perfect matching.In many famous networks,there will be perfect matching or an almost perfect matching.However,with the increase of processor number,the probability and randomness of failure in the network become greater and greater,So whether there is perfect matching or almost perfect matching in the failed network has been widely studied.So Brigham[1]et al.proposed matching preclusion.Let F be a set of fault edges of graph G,if G-F contains neither a perfect matching nor an almost perfect matching,then F is called a matching preclusion set of graph G.Any such optimal edge set is called an optimal matching preclusion set.The set of all edges associated with the minimum degree point is the optimal trivial matching preclusion set.In ultra large parallel computers,the network failures are random,that is to say,the probability of all the links connected with a point in the network failure is very small.Therefore,the concept of conditional matching preclusion number is proposed by Cheng[2]et al.and has been widely studied.The conditional matching preclusion number of graph G is defined as the minimum number of edges,so that the graph obtained by deleting these edges has no perfect matching and almost perfect matching,and no isolated vertex.The set of these edges is called the conditional matching preclusion set of graph G.Any conditional matching preclusion set whose size is equal to conditional matching preclusion number is called an optimal conditional matching preclusion set.Take any two-long path u-w-v in the graph G,let（EG（u）∪ EG（v））\EG（w）be a conditional matching preclusion set of graph G,then such conditional matching preclusion set is called a trivial conditional matching preclusion set.The modified bubble sort graph is a topological structure of an interconnection network,which contains n! vertices and（n·n!）/2 edges.Consider a connected simple graph H of order n≥ 3,its vertex set is {1,2,…,n｝,and each of it can be regarded as a swap in the symmetry group Sn,so that the edge set E（H）of H corresponds to a swap set in Sn.In this case,H is called commutative simple graph.The corresponding Cayley graph of the commutative simple graph H is denoted as Cay（H,Sn）.When a commutative simple graph is a unicyclic graph,the corresponding Cayley graph is called the Cayley graph generated by unicyclic graph,which is recorded as UGn.In particular,when H is a circle,UGn is called modified bubble sort graph,denoted as MBn.In this article,we mainly studied the conditional matching preclusion of modified bubble sort graphs,and the main results are as follows:（1）The conditional matching preclusion number of modified bubble sort graph MBn is 2n-2;（2）The optimal conditional matching preclusion sets of modified bubble sort graphs MBn are trivial;（3）The strong matching preclusion number of the modified bubble sort graph MBn is 2,and the strong conditional matching preclusion number is 2.