Edge Fault-Tolerant Strong Hamiltonian Laceability of Balanced Hypercubes

摘要

The balanced hypercube BH_n, proposed by Wu and Huang, is a new variation of hyper-cube. A Hamiltonian bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path between two arbitrary vertices from different partite sets. A Hamiltonian laceable graph G is strongly Hamiltonian laceable if there is a path of length |V(G)| - 2 between any two distinct vertices of the same partite set. A graph G is called k-edge-fault strong Hamiltonian laceable, if G - F is strong Hamiltonian laceable for any edge-fault set F with |F| ≤ k. It has been proved that the balanced hypercube BH_n is strong Hamiltonian laceable. In this paper, we improve the above result and prove that BH_n is (n - 1)-edge-fault strong Hamiltonian laceable.