Hamiltonian paths passing through matchings in hypercubes with faulty edges

被引:0
作者
Zhao, Shenyang [1 ]
Wang, Fan [1 ]
机构
[1] Nanchang Univ, Sch Math & Comp Sci, Nanchang 330000, Jiangxi, Peoples R China
来源
AIMS MATHEMATICS | 2024年 / 9卷 / 12期
关键词
hypercube; Hamiltonian path; matching; faulty edges; PRESCRIBED EDGES; CYCLES; BIPANCYCLICITY; EXTEND;
D O I
10.3934/math.20241608
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 n >= 4, let M be a matching of Qn, and let F be a set of edges in Qn - M with M boolean OR F <= 2n - 6. Let x and y be two vertices of Qn with different parities satisfying xy M. If all vertices in Qn - F have a degree of at least 2, then there exists a Hamiltonian path joining x and y passing through M in Qn - F, with the exception of two cases: (1) there exist two neighbors v and t of x (or y) satisfying dQn-F(v) = 2 and xt E M (or yt E M); (2) there exists a path xvuy of length 3 satisfying dQn-F(v) = 2 and uy E M or dQn-F(u) = 2 and xv E M.
引用
收藏
页码:33692 / 33711
页数:20
相关论文
共 23 条