Some Properties Of Perfect Matchings Of 4 Ary N Cubes

The k-ary n-cube is one of the most popular interconnection networks with many excellent characteristics. The k-ary n-cube is denoted by Qnk(k≥2,n≥1).The set of vertices V(Qnk)={u0u1…un-1]:0≤ui≤k-1,0≤n-1}. Two vertices u=u0u1…un-1 and v=vov1…vn-1 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∈{0,1,…n-1)\{j}..Note(u,v)is an edge which dimension is j.If deleting all edges which dimensions are j of Qn4,j∈{0,1,2,…n-1),there are four 4 ary n cubes Q[0].Q[1].Q[2]å'ŒQ[3].A set of edge M of a graph G is a matching if every vertex of G is incident with at most one edge of M.If a vertex is incident with an edge of M,then this vertex is covered by M,otherwise,this vertex is uncovered by M.A matching M is perfect if every vertex of G is covered by M.The matching graph M(G) of a graph G has a vertex set of all perfect matchings of G,with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle.Then there is a natural one-to-one correspondence between perfect matchings of G and vertices of M(G).Perfect matchings can be applied to network disclosure.When tracing messages sent through a threshold mix in arbitrary scenarios,the perfect matchings disclosure attack will operate a high rate success.Matching preclusion is related to the problem of connectivity of networks.In this paper,we study some problems of perfect matchings of 4 ary n cubes. The article is divided into three chapters:In Chapter 1.we introduce some basic concepts.In Chapter 2,we study the problem of a matching extending to a perfect matching of Qn4.The main results are as follows.(1)Let M be an arbitrary with at most 2n-1 edges in a Qn4.Then the matching M can be extended to a perfect matching of Qn4.(2)Let M be an arbitrary with at most 2n-2 edges in a Qn4,there must exist d∈{0,1,…,n-1},such that M contain at most one edge which dimension is d.If deleting all edges which dimensions are j of Qn4,J∈{0,,2,…,n-1),there are four 4 ary n cubes Q[0].Q[1].Q[2]å'ŒQ[3].If x,y be any two unmatched vertices in one Q[j],i∈{0,1,2,3},and the length between them is odd.Then the matching M can be extended to a perfect matching of Qn4\{x,y}. In Chapter 3,we study some properties of the matching graph of Qn4.The main result is as follows.Note[n]={0,1,…,n-1).For arbitraryα∈[n],note Inα1={(u0u1…ua-11uα+1. un-1,u0u1…uα-12uα+1…un-1)|ui∈[4],i∈[n]\{α}∪{(u0u1…uα-1Ouα+1…un-1,u0u1…uα-13uα+1…un-1)|ui∈[4],i∈[n]\{α}),lnα2={(uou1…uα-12uα+1…un-1,u0u1. uα-13uα+1…un-1)|ui∈[4],i∈[n]\{α}>∪{(u0u1…uα-1Ouα+1…un-1,u0u1…uα-I1 uα+1…un-1)|ui∈[4],i∈[n]\{α}},then Inα1 and Inα2 are perfect matchings of Qn4.Let Inαi and Inβi be two perfect matchings of Qn4,i,j∈{1,2},α,β∈{0,1,2,…,n-1}.Then, there must exist a walk which length is at most 6 between Inαi and Inβi.