Publications
Sort:
Open Access Research Article Issue
Hamiltonian paths passing through matchings in hypercubes with faulty edges
AIMS Mathematics 2024, 9(12): 33692-33711
Published: 15 December 2024
Abstract PDF (338.3 KB) Collect
Downloads:2

Chen considered the existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cube Qn. In this paper, we considered the existence of a Hamiltonian path and obtained the following result. For n4, let M be a matching of Qn, and let F be a set of edges in QnM with |MF|2n6. Let x and y be two vertices of Qn with different parities satisfying xyM. If all vertices in QnF have a degree of at least 2, then there exists a Hamiltonian path joining x and y passing through M in QnF, with the exception of two cases: (1) there exist two neighbors v and t of x (or y) satisfying dQnF(v)=2 and xtM (or ytM); (2) there exists a path xvuy of length 3 satisfying dQnF(v)=2 and uyM or dQnF(u)=2 and xvM.

Total 1