Edge-fault-tolerant Hamiltonicity Of (n,k)-star Graphs Under The Conditional Fault Model

As a variant of Cayley graphs,(n, k)-star graph has many good properties. It 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. This thesis consists of three chapters, the goal of which is to study the conditional edge fault Hamiltonicity of (n, k)-star graph.The first chapter is the introduction, we introduce some useful notation, the back-ground and significance of the article topics. It also presents the definition and related properties of the (n, k)-star graph.In addition, some of the conclusions about the (n, k)-star graph are included.In the second chapter, we investigate the edge-fault-tolerant Hamiltonicity of the (n,k)-star graph under the conditional fault model when k=n-2. We will show that (n, n-2)-star graph is (2n-7)-edge fault-tolerant Hamiltonicity under the conditional fault model by induction on n.In the third chapter, we investigate the edge-fault-tolerant Hamiltonicity of the (n,k)-star graph under the conditional fault model when k≤n-3. In the first, we show the case of k=3. Since Sn,3can be divided into n Sn-1,2i-subgraphs, without loss of generality, we consider the faulty edges in sn-1,21we show the conclusion that Sn,3is (2n-8)-edge fault-tolerant Hamiltonicity under the conditional fault model by discussing the case of the conditional faulty edges. In the following, we show that Sn,k is (2n-8)-edge fault-tolerant Hamiltonicity under the conditional fault model by induction on n and k. Furthermore, our result is optimal.Finally, we give a conclusion and show the problems that can be studied in the future.