Research On The Problem Of Fractional Matching Preclusion Of The Recursive Circulant Graph

The connection between computer and computer is called network topology in a net-work system.We can transform the problem of studying the topological structure of the interconnection network into that of studying the corresponding structural graph,and use the structural properties of the graph to simulate the performance of the topological structure of the interconnection network.Each processor can be assigned a matching processor at any time such that the network can be guaranteed by the cooperation be-tween these processor pairs in some specific networks.A natural problem:the resulting graph has no perfect match after how many edges need to be deleted at least,which is the graph matching exclusion problem.Matching preclusion is a measure of robustness in the event of edge failure in interconnection networks.As a generalization of match-ing,fractional matching preclusion number of a graph is the minimum number of edges need to be deleted such that the resulting graph has no fractional perfect matching.In this paper,we establish the fractional matching preclusion number and the fractional strong matching preclusion number of the recursive circulant graph G(dn,d)for n? 2,d?3 and G(2n,4)for n? 3.It is divided into 5 chapters in this paper.The research background of fractional matching preclusion,related concepts and symbols are intro-duced in chapter 1.In chapter 2,we introduce recursive circulant graphs and lemmas needed in this paper.we investigate the fractional matching preclusion number and the fractional strong matching preclusion number of the recursive circulant graph G(dn,d)for n? 2,d? 3 in chapter 3.In chapter 4,the fractional matching preclusion number and the fractional strong matching preclusion number of the recursive circulant graph G(2n,4)for n? 3 are determined.Our conclusions are given in chapter 5.