Hamiltonian cycles of balanced hypercube with more faulty edges

DOI10.1016/J.TCS.2023.113708arXiv2208.08601MaRDI QIDQ6408168

Ting Lan, Huazhong Lü

Publication date: 17 August 2022

Abstract: The balanced hypercube $B{H}_n$, a variant of the hypercube, is a novel interconnection network for massive parallel systems. It is known that the balanced hypercube remains Hamiltonian after deleting at most $4n-5$ faulty edges if each vertex is incident with at least two edges in the resulting graph for all $ngeq2$. In this paper, we show that there exists a fault-free Hamiltonian cycle in $B{H}_n$ for $nge2$ with $left|Fight|le5n-7$ if the degree of every vertex in $B{H}_n-F$ is at least two and there exists no $f_4$-cycles in $B{H}_n-F$, which improves some known results.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Reliability, testing and fault tolerance of networks and computer systems (68M15) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

This page was built for publication: Hamiltonian cycles of balanced hypercube with more faulty edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408168)