The Matching Preclusion For K-ary N-cubes And Augmented K-ary N-cubes

A set F of edges in G is called a (conditional) matching preclusion set if G-F (with no isolated vertices) has neither perfect matchings nor almost perfect matchings. Any such optimal set is called an optimal (conditional) matching preclusion set. The (conditional) matching preclusion number of G, is the cardinality of a minimum (con-ditional) matching preclusion set in G. For a graph G of even order, EG(x) forms a matching preclusion set for x∈V(G) and (EG(u)∪EG(w))\EG(v) is a conditional matching preclusion set for uv, vw∈E(G). A matching preclusion set of a graph is trivial if all its edges are incident to a single vertex. A conditional matching preclusion set F of a graph G is trivial if F=(EG(u)∪EG(w))\EG(v), where uv, vw∈E(G).This paper which stands on the basis of previous results, do further research on the (conditional) matching preclusion for k-ary n-cubes and augmented k-ary n-cubes. This thesis consists of three chapters.In Chapter1, we introduce some useful graph-theoretical terminology and nota-tion, the background and significance of the matching preclusion, the development of a representative at home and abroad regarding this aspect.In Chapter2, let k≥4be even, we show that the optimal conditional matching preclusion set of Torus(k, k) is trivial. Furthermore, the optimal conditional match-ing preclusion set of k-avy3-cubes is trivial. Then the optimal conditional matching preclusion set of k-ary n-cubes is trivial, where n≥2.In Chapter3, let n≥2and k≥4be even, we show that the matching preclusion number and the conditional matching preclusion number of the augmented k-ary n-cubes are4n-2and8n-7respectively. Furthermore, the optimal (conditional) matching preclusion set of augmented k-ary n-cubes is trivial.Finally, conclusion and some problems to be studied further are proposed in the thesis.