The Matching Preclusion for kary ncubes and Augmented kary ncubes 

Author  ZhangZuoYuan 
Tutor  LiuHuiQing 
School  Hubei University 
Course  Operational Research and Cybernetics 
Keywords  perfect matching almost perfect matching kary ncubes augmentedkary ncubes matching preclusion conditional matching preclusion 
CLC  O157.5 
Type  Master's thesis 
Year  2012 
Downloads  4 
Quotes  0 
A set F of edges in G is called a (conditional) matching preclusion set if GF (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 (conditional) 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 kary ncubes and augmented kary ncubes. This thesis consists of three chapters.In Chapter1, we introduce some useful graphtheoretical terminology and notation, 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 matching preclusion set of kavy3cubes is trivial. Then the optimal conditional matching preclusion set of kary ncubes 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 kary ncubes are4n2and8n7respectively. Furthermore, the optimal (conditional) matching preclusion set of augmented kary ncubes is trivial.Finally, conclusion and some problems to be studied further are proposed in the thesis.