The Local-connectivity And The Matching Preclusion For Bubblesort Star Graphs

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links respectively. Connectivity is an important measurement for the fault tolerant in interconnection network. Two vertices are maximally local-connected if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. If any two vertices are maximally local-connected in a graph, the graph is called maximally local-connected. Consider that there are fault vertices in a graph, the graph is called fault tolerance maximally local-connected, if any two vertices are maximally local-connected in a graph deleting the fault vertices. The problem about the matching of a graph is very popular in the study of network theory. The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matching nor almost-perfect matching.The bubblesort star graph is a new interconnection network, which is the merger of the famous bubblesort graph and the star graph. So the bubblesort star graph combine the advantages of both graphs. In this paper, we mainly research the fault-tolerant maximal local-connectivity and matching preclusion number for the bubblesort star graphs. The main results are as follow:(1) an n-dimensional bubblesort star graph is (2n-5)-fault-tolerant maximally local-connected and (2n-6)-"one to many" fault-tolerant maximally local-connected. In addition, the conclusion given by the article is optimal.(2) we find matching preclusion number for the bubblesort star graphs and every optimal matching preclusion set is trivial.