Matching Preclusion For The Two-dimensional Torus

Let m, n≥2 be two integers, the two-dimensional m×n torus denoted by Torus(m, n) is a graph consisting of mn vertices. The set of vertices is{va,b:0≤α≤m-1,0≤b≤n-1}. Two vertices va,b and v a′,b′are adjacent if and only if either a=a′and b= b′±1 (mod n) or b= b′and a= a′±1 (mod m).A set F of edges in G is called a matching preclusion set if G - F has neither a perfect matching 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 trivial if all its edges are incident to a single vertex. For many interconnection networks, the minimum matching preclusion sets are trivial. A set F of edges in G is called a conditional matching preclusion set if G-F has no isolated vertices and 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. In this paper, we find the matching preclusion numbers (resp. sets) and conditional matching preclusion numbers (resp. sets) of the two-dimensional torus. The article is divided into three chapters:In Chapter 1, we introduce some useful basic concepts and propositions.In Chapter 2, we study the matching preclusion numbers (resp. sets) and conditional matching preclusion numbers (resp. sets) of Torus(k1,k2), where even k1≥2 and odd k2≥3. The main results are as follows:(1) If the length of an odd cycle is not less than 3, then the matching preclusion number of the odd cycle is 3.(2) Let k2≥3 be odd. Then both the matching preclusion number and conditional matching preclusion number of Torus(2, k2) are 3.(3) Let k1≥4 be even and k2≥3 be odd. Then the matching preclusion number of Torus(k1,k2) is 4. Moreover, every minimum matching preclusion set is trivial.(4) Let k1≥4 be even and k2 = 3. Then, the conditional matching preclusion number of Torus(k1,3) is 5.(5) Let k1≥4 be even and k2≥5 be odd. Then, the conditional matching preclusion number of Torus(k1,k2) is 6.The k-ary n-cube, denoted by Qnk (k≥2 and n≥1), is a graph consisting of kn vertices. The set of vertices is{un-1un-2…u0:0≤ui≤k-1,0≤i≤n-1}. Two vertices u=un-1un-2…u0 and v=vn-1vn-2…v0 are adjacent if and only if there exists an integer j∈{0,1,…,n-1}such that uj=vj±1(mod k)and ui=vi for every i∈{1,2,…,n}＼{j}.Obviously,Q2k is isomorphic to Torus(k,k).In Chapter 3,we find the matching preclusion number of the k-ary 2-cube,where odd k≥3.The main result is as follows:Let k≥3 be odd.Then the matching preclusion number of the k-ary 2-cube is 7.