Bipancyclicity And Path Covers Of Two Kinds Of Networks

The topology of the interconnection network is a graph. Cycle embedding has always been a hot research field in graph theory and computer science for the low cost and wide application of networks with the ring topology. Pancyclic is an extension of the cycle embedding, which is finding the cycle with every length from girth to the order of a graph. Both processors and the links of the network can be disabled in the work, studying fault-tolerant pancyclicity has great practical significance. The paths are disjoint if any two of them have no common vertex. Furthermore, the disjoint path cover is a set of disjoint paths that altogether cover every vertex of the graph. In networks, it means all the vertices in the networks can be participated in parallel computing. The study of disjoint path cover contributes to the optimization and utilization of network resources and can be applied in many areas such as software testing, code optimization and database design.The hypercube is the preferred structure of parallel processing and parallel computing system. With the development of information technology, the require-ment of the network structure is more and more high, many variations of the hypercube, such as balanced hypercubes, folded hypercubes and so on have been proposed, they have many advantages than the hypercube.In this paper, we study the edge fault-tolerant bipancyclicity in hypercubes and path covers in balanced hypercubes. This thesis is organized as follows.Chapter 1 is an introductive part. We introduce some basic definitions used in this thesis, and the background and some known results about edge fault-tolerant bipancyclicity and path covers of graphs.In Chapter 2, we introduce the two kinds of networks—hypercubes and bal-anced hypercubes in detail, and give the definitions, several concepts and proper-ties related to our research.In Chapter 3, we prove the edge fault-tolerant bipancyclicity of hypercubes. Let F be a set of faulty edges in Qn for n≥ 6 with |F|≤ 3n - 7, there exists a fault-free cycle of every even length from 4 to 2n in Qn, if condition (1) each vertex is incident to at least two fault-free edges and condition (2) Qn - F has neither f4-cycle nor f6-cycle are been satisfied.In Chapter 4, we prove the paired 3-disjoint path covers in balanced hyper-cubes. For n ≥ 3, let S ? B and T ? W, where B and W are two distinct partite sets of BHn, then BHn has a paired 3-disjoint path cover relative to S U T. This is an extention of the result obatained by Cheng et al. in [Applied Mathematics and Computation,2014,242:127-142].Chapter 5 is the conclusion of the thesis. The main results in this paper are summarized and the further research directions are given.