Optimal Edge Fault-tolerant-prescribed Hamiltonian Laceability Of Balanced Hypercubes

Parallel computer systems are always built based on a graph with excellent graph theory properties,which is called the interconnection network of parallel computer systems（referred to as network）.In the interconnection network,there is an important type of problem,which is structure simulation,that is to simulate the behavior of another network in one network.The structural simulation problem is also called the network embedding problem.Linear arrays（paths）and rings（cycles）are the two most basic network topologies in the field of parallel distributed computing.Therefore,the embedding of paths and cycles in the network is of great significance.In practical system application,processor and communication line failures in the network are inevitable.At this time,embedding paths and cycles in the network needs to avoid these failures,which is called fault-tolerant embedding.In the actual network,some communication lines may have better performance than other lines.Therefore,when embedding paths and cycles in the network,engineers hope to pass these better communication lines as much as possible.This kind of embedding is called prescribed embedding.Sometimes,the actual system contains both fault elements and communication lines with better performance.In this case,when embedding paths and cycles,it is necessary to avoid faults and pass through better communication lines.This kind of embedding is called fault-tolerant-prescribed embedding.Let G be a bipartite interconnection network with bipartition（X,Y）,F C E（G）be a set of faulty edges,and L be a linear forest in G-F,such that |F|+|E（L）|≤m.Let u（?）X and v（?）Y be arbitrary two vertices such that none of the paths in L has u or v as internal vertices or both of them as end vertices.G is said to be m-fault-tolerant-prescribed hamiltonian laceable if G-F admits a hamiltonian path between u and v passing through L.The n-dimensional balanced hypercube network（BH_n）is one of the most competitive candidate networks in parallel computer systems.Each vertex in it has a backup vertex that is the same as its neighborhood.In this article,we mainly study the fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes,and prove that BH_n is（2n-2）-fault-tolerant-prescribed hamiltonian laceable.