Conditional Matching Preclusion For Some Interconnection Networks

Advances in technology have made it possible to build a large-scale parallel system involving thousands of processors.One crucial step on designing a system is to determine the underling topology of the system.The network topology determines the performance of the system.The HL-graph and k-ary n-cube are two of the most popular networks.Given two graphs G0and G1with n vertices each,we denote by Vj and Ej the vertex set and edge set of Gj, j=0,1, respeetively. Let V0={v1, v2,…,vn} and V1={w1, w2,…, wn}. With respect to a permutation P=(i1, i2,..., in) of {1,2,…, n}, we can merge the two graphs into a graph G0(?)pG1with2n vertices in such a way that the vertex set V=V0(?)V1and the edge set E=E0(?)E1(?) E2, where E2={vjwij|1≤j≤n}. We denote by G0(?)G1a graph obtained by merging G0and G1with respect to an arbitrary permutation P. Let H L0=K1; for m≥1, H Lm={G0(?) G1|G0,G1∈H Lm-1}. An arbitrary graph which belongs to H Lm is called m-dimensional HL-graph.The bipartite graph in m-dimensional HL-graph is called m-dimensional bipartite HL-graph.The k-ary n-cube Qnk(k≥2andn≥2) is a graph consisting of kn vertices, each of which has the form u=u0u1… un-1, where0≤ui≤k-1for0≤i≤n-1. Two vertices u=u0u1… un-1and v=v0v1… vn-1are adjacent if and only if there exists an integer j,0≤j≤n-1, such that uj=vj±1(mod k) and ui=ui, for every i∈{0,1,…,n-1}＼{j}.Along with the increasing of processors,failures of network components are in-evitable. It is significant to consider faulty networks if it keeps the original good properties or not. Having perfect matching and almost perfect matching is an important aspect.A set F of edges in G is called a matching preclusion set if G-F has neither a perfect matchillg nor an almost perfect matching. The matching preclusion number of G is the cardinality of a minimum matching preclusion set in G. An edge set of a graph is called a trivial matching preclusion set if all its edges are incident to a single vertex. A set F of edges in G is called a conditional matching preclusion set if G-F has no isolated vertices alld has neither a perfect matching nor an almost perfect matching. The conditional matching preclusion number of G is the cardinality of a minimum conditional matching preclusion set in G. Pick out any path¨u-v-w in G, an edge set of a graph is called a trivial conditional matching preclusion set if all its edges are incident to either u or w but not v. In this paper, we study the conditional matching preclusion number and the optimal conditional matching preclusion set for bipartite HL-graph and k-ary n-cubes. The thesis is divided into three chapters:In chapter1, we introduce some useful basic concepts and propositions.In chapter2, we study the optimal conditional matching preclusion set for bipartite HL-graph. We proved that the optimal conditional matching preclusion set is trivial.In chapter3, we study the conditional matching preclusion number and the optimal conditional matching preclusion set for k-ary n-cubes. The main results are as follows:(1) The conditional matching preclusion number for3-ary2-cube is6, and the optimal conditional matching preclusion set is depicted.(2) Let k≥4be an even integer. Then the optimal conditional matching preclusion set for k-ary n-cubes is trivial.