Path embeddings with prescribed edge in the balanced hypercube network (Q2333505)

Summary: The balanced hypercube network, which is a novel interconnection network for parallel computation and data processing, is a newly-invented variant of the hypercube. The particular feature of the balanced hypercube is that each processor has its own backup processor and they are connected to the same neighbors. A Hamiltonian bipartite graph with bipartition \(V_0 \cup V_1\) is Hamiltonian laceable if there exists a path between any two vertices \(x \in V_0\) and \(y \in V_1\). It is known that each edge is on a Hamiltonian cycle of the balanced hypercube. In this paper, we prove that, for an arbitrary edge \(e\) in the balanced hypercube, there exists a Hamiltonian path between any two vertices \(x\) and \(y\) in different partite sets passing through \(e\) with \(e \ne x y\). This result improves some known results.