The Conditional Fault Tolerance Of Burnt Pancake Graphs

As a variant of Cayley graphs, the burnt pancake graph has many good properties. The degree and diameter are smaller than a hypercube with similar number of vertices. Then the burnt pancake graph is proposed as an important interconnection network topology and can be used for massively parallel systems.Let G be a graph and F(?)E(G). G is f-conditional edge fault Hamiltonian if G-F is Hamiltonian for any|F|<f and δ(G-F)≥2. F is called a matching preclusion set if G-F has neither perfect matchings nor almost perfect matchings. The matching preclusion number of G, is the cardinality of a minimum matching preclusion set in G. F is called a conditional matching preclusion set if G-F has no isolated vertices and has neither perfect matchings nor almost perfect matchings. The matching preclusion number of G, is the cardinality of a minimum matching preclusion set in G. This thesis consists of three chapters, the goal of which is to study the conditional edge fault Hamiltonicity and the matching preclusion and conditional matching preclusion of burnt pancake graphs.In the first chapter, we first introduce some useful basic concepts and propositions, and then give an introduction to the background of the research and results in this paper.In the second chapter, we show that the burnt pancake graph is (2n-5)-edge fault Hamiltonian, where n is the dimensional of the burnt pancake graph.In the third chapter, we show that the matching preclusion number of the burnt pancake graph is n and every minimum matching preclusion set is trivial, the condi-tional matching preclusion number of the burnt pancake graph is2n-2and every minimum conditional matching preclusion set is trivial, where n is the dimensional of the burnt pancake graph.Finally, conclusion and some problems to be studied further are proposed in the thesis.