Many-to-many Disjoint Path Covers In Restricted Hypercube-like Graphs

Restricted hypercube-like graph is a very important network topology struc-ture. The disjoint path cover problem is an important research topic. A paired many-to-many k-disjoint path cover(k-DPC for short) of a graph is a set of k disjoint paths joining k distant source-sink pairs that cover all the vertices of the graph. If there are some fault vertices or edges in the graph, then the paths can-not through them. In this paper, we discuss the disjoint path cover of the lower dimensional restricted hypercube-like graph and we, based on the conclusion of 2-DPC, show that every m-dimensional restricted hypercube-like graph, RHLm, under the condition that m-5 or less faulty elements (vertices and/or edges) are removed, has a paired many-to-many 3-DPC joining any 3 distinct source-sink pairs where m> 6.There are three chapters in this paper:Chapter 1 is an introduction part. We introduce some basic definitions of graph theory, the relative background and approaches of our research and main works.Chapter 2 introduces the definition and properties of the restricted hypercube-like graph. In the first Section, we give the definition of the restricted hypercube-like graph and locally twisted cubes; In the second Section, we give the properties and conclusions, about the degree of vertex set, embedding of pathes and cycles, and hamiltonian path, of the restricted hypercube-like graphs.Chapter 3 gives further analysis for the disjoint path covers of restricted hypercube-like graphs, discusses the disjoint path covers of the lower dimensional restricted hypercube-like graphs, gives the examples about three and four dimen-sional restricted hypercube-like graphs are not the disjoint path coverable and proves that every m-dimensional restricted hypercube-like graph, RHLm, under the condition that m-5 or less faulty elements(vertices and/or edges) are removed, has a paired many-to-many 3-DPC joining any 3 distinct source-sink pairs where m≥ 6.