The Properties Of Exchanged Folded Hypercube

An interconnection network is always represented as an undirected graph G=(V,E),where V represents the set of processors and E is the set of communication links between processors.The n-dimensional hypercube,which is denoted by Qn,is one of the most popular and effective interconnection network structures.It has fine excellent properties,making it the first structure of parallel processing and parallel computing systems,and has a wide range of applications in industry.In order to further improve the performance of hypercubes,variant structures are proposed based on hypercubes.In fact,hypercubes have two types of variants.The first is to improve connectivity and shorten transmission delay,which can be achieved by adding some edges into the standsrd hypercubes.The second is to reduce cost and complexity.In this case,some edges can be deleted from hypercubes.The n-dimension folded hypercubes proposed by Ahmed EL-Amawy is formed by adding edges on the basis of the hypercubes structure,and proved that the diameter of the n-dimensional folded hypercubes is about half of that of the n-dimensional hypercubes.However,due to the large number of edges in the folded hypercubes,the hardware cost increases.To reduce the number of edges and thus reduce the cost and complexity,Loh proposed an exchanged hypercubes EH(s,t),which is formed by removing edges from the hypercubes.Not only does it maintain many of the superior properties of the hypercube network,but it effectively reduces the number of sides of the hypercube by nearly half.Although the exchanged hypercubes highly reduces the complexity of the interconnection network,it still has some drawbacks.For example,the diameter of exchanged hypercubes is much longer than in the folded hypercubes.In order to improve the performance of the exchanged hypercubes and the folded hypercubes,a new interconnection topology structure named exchanged folded hypercubes was proposed by Heng Qi,which is formed by adding some edges to link a node with its farthest node from exchanged hypercubes,the edges added are noted as complementary edges.The exchanged folded hypercubes not only retains most of the topological features of the exchanged hypercubes structure,but also combines many of the advantages of the folded hypercubes structure.The network diameter of exchanged folded hypercubes is about half of the diameter of exchanged hypercubes;the number of edges in EFH(s,t)is near 1/2 of that of an(s+t+1)-dimension folded hypercubes when the dimension is large;The exchanged folded hypercubes has outstanding cost factors,shorter latency,and less information traffic density.In this paper,some conclusions are drawn by studying the structural properties of exchanged folded hypercubes.The main contents of this paper are as follows:(1)In this paper,the domination numbers of the exchanged folded hypercubes are studied,and provide some upper bounds for the domination number of exchanged folded hypercubes:?(EFH(s,t)?2^s+t-2+(2^s-2s-2)?(Q_t),when s,t?1,s?2,?(EFH(s,t)?(2^s-4)?(Q_t)+2t(1+?(Qs-c)),when 2?s?t,t?3,?(EFH(s,t))?(2^s-2p)?(Q_t)+2t(1+?(Qs-c)),where p=[log2(t+1)].(2)We investigate the vertex-transitive of exchanged hypercubes EH(s,t),In the exchanged hypercubes EH(s,t),let EH(s,t)=(V,E),its vertices can be partitioned two disjoint subsets V=V₀?V₁ and V₀?V₁=?,where V₀={as…a₁bt…b₁0},V₁={as…a₁bt…b₁1}.Then the vertices of Vc(c?{0,1})are vertex-transitive;and there are s×t isomorphisms between EH(s,t)and EH(t,s).(3)We investigate the vertex-transitive of exchanged folded hypercubes EFH(s,t),In the exchanged folded hypercubes EFH(s,t),let EFH(s,t)=(V,E),its vertices can be partitioned two disjoint subsets V=V₀?V₁ and V₀?V₁=?,where V₀={as…a₁bt…b₁0},V₁={as…a₁bt…b₁1}.Then the vertices of Vc(c?{0,1})are vertex-transitive;and there are s×t isomorphisms between EFH(s,t)and EFH(t,s).(4)Studying the problem of internal disjoint paths in EFH(s,t),constructing(s+2)internal disjoint paths between any two vertices in EFH(s,t),and prove that?(EFH(s,t))=?(EFH(s,t))=s+2,where 1?s?t.(5)The edge-hamiltonicity of EFH(s,t)is studied,and it is proved that each edge of EFH(s,t)lies on an Hamilton cycle.