Computational Complexity Of Conditional Matching Preclusion Problem And Some Network Properties Of Balanced Hypercubes

What most effects the performance of a large scale parallel and distributed sys-tems is the topology structure of the processors being interconnected, which is called interconnection network, for short, network. Since the topology of a network is a graph, vertices represent processors or storage, and edges represent physical links be-tween processors or storage. The advantage for using graph theory to design and analyze the performance of the interconnection networks is natural and powerful. In this thesis, we mainly use graph theory to study the properties of balanced hypercubes and computational complexity of matching preclusion number problem as well as its related problems.This thesis contains six chapters. In Chapter1, firstly, we introduce some ba-sic definitions and notations of interconnection networks and graph theory. Then the definitions of (conditional) matching preclusion set and anti-Kekule set are given. Fol-lowing the definitions and terminologies of computational complexity are also given. Next, we introduce the concept of the balanced hypercube and its research background and some properties. Finally, we list the main results of this thesis.In Chapter2, we study computational complexity of the (conditional) match-ing preclusion problem and anti-Kekule problem. By definition, we show that the matching preclusion problem on bipartite graphs with perfect matching is equivalent to a type of problem called minimum blocker perfect matching problem. It is known that minimum blocker perfect matching problem on bipartite graphs is NP-complete. Thus, the matching preclusion problem on bipartite graph with perfect matching is also NP-complete. We prove the NP-completeness of anti-Kekule problem on bipar-tite graphs by polynomial transforming the matching preclusion problem on bipartite graphs to it. As a corollary, we prove the conditional matching preclusion problem is NP-complete. At the end of this chapter, as an extension of matching preclusion. we propose a concept called s-restricted matching preclusion problem (s≥1is an integer). We also prove that s-restricted matching preclusion problem is NP-complete.In Chapter3, we study the (conditional) matching preclusion number of the balanced hypercube. We determine that for all positive integers n, the matching preclusion number of BHn is2n, and all the matching preclusion set of BHn with cardinality2n are trivial. Moreover, we also show that the conditional matching preclusion number of BHn is4n-2.In Chapter4, we propose a Cayley graph model for BHn, accordingly BHn is Cayley graph. This improves the preceding result of BHn being vertex-transitive. We also give a shortest routing algorithm of BHn by our Cayley graph model of BHn.In Chapter5, we study the restricted (edge) connectivity of BHn. We determine that the2-restricted (resp.3-restricted) edge connectivity of BHn is4n-2(resp.6n-4) when n≥2. We also show that2-restricted connectivity of BHn is4n-4.In Chapter6, we mainly study a class of Hamiltonian path embedding problem of BHn. It is known that BHn is Hamiltonian laceable and bipancomected. We show that BHn is hyper-Hamiltonian laceable for all n≥1.