Hamiltonian paths passing through matchings in hypercubes with faulty edges
Chen considered the existence of a Hamiltonian cycle containing a matching and avoiding some edges in an $ n $-cube $ Q_n $. In this paper, we considered the existence of a Hamiltonian path and obtained the following result. For $ n\geq4 $, let $ M $ be a matching of $ Q_n $, and let $ F $ be a set...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2024-11-01
|
| Series: | AIMS Mathematics |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/math.20241608 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Chen considered the existence of a Hamiltonian cycle containing a matching and avoiding some edges in an $ n $-cube $ Q_n $. In this paper, we considered the existence of a Hamiltonian path and obtained the following result. For $ n\geq4 $, let $ M $ be a matching of $ Q_n $, and let $ F $ be a set of edges in $ Q_n-M $ with $ |M\cup F|\leq2n-6 $. Let $ x $ and $ y $ be two vertices of $ Q_n $ with different parities satisfying $ xy\notin M $. If all vertices in $ Q_n-F $ have a degree of at least $ 2 $, then there exists a Hamiltonian path joining $ x $ and $ y $ passing through $ M $ in $ Q_n-F $, with the exception of two cases: (1) there exist two neighbors $ v $ and $ t $ of $ x $ (or $ y $) satisfying $ d_{Q_n-F}(v) = 2 $ and $ xt\in M $ (or $ yt\in M $); (2) there exists a path $ xvuy $ of length 3 satisfying $ d_{Q_n-F}(v) = 2 $ and $ uy\in M $ or $ d_{Q_n-F}(u) = 2 $ and $ xv\in M $. |
|---|---|
| ISSN: | 2473-6988 |