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!
|
| _version_ | 1832590763315167232 |
|---|---|
| author | Shenyang Zhao Fan Wang |
| author_facet | Shenyang Zhao Fan Wang |
| author_sort | Shenyang Zhao |
| collection | DOAJ |
| description | 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 $. |
| format | Article |
| id | doaj-art-a0d4d026487444a2bb4e7b87d21807f6 |
| institution | Kabale University |
| issn | 2473-6988 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | AIMS Mathematics |
| spelling | doaj-art-a0d4d026487444a2bb4e7b87d21807f62025-01-23T07:53:24ZengAIMS PressAIMS Mathematics2473-69882024-11-01912336923371110.3934/math.20241608Hamiltonian paths passing through matchings in hypercubes with faulty edgesShenyang Zhao0Fan Wang1School of Mathematics and Computer Sciences, Nanchang University, Nanchang, Jiangxi 330000, PR ChinaSchool of Mathematics and Computer Sciences, Nanchang University, Nanchang, Jiangxi 330000, PR ChinaChen 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 $.https://www.aimspress.com/article/doi/10.3934/math.20241608hypercubehamiltonian pathmatchingfaulty edges |
| spellingShingle | Shenyang Zhao Fan Wang Hamiltonian paths passing through matchings in hypercubes with faulty edges AIMS Mathematics hypercube hamiltonian path matching faulty edges |
| title | Hamiltonian paths passing through matchings in hypercubes with faulty edges |
| title_full | Hamiltonian paths passing through matchings in hypercubes with faulty edges |
| title_fullStr | Hamiltonian paths passing through matchings in hypercubes with faulty edges |
| title_full_unstemmed | Hamiltonian paths passing through matchings in hypercubes with faulty edges |
| title_short | Hamiltonian paths passing through matchings in hypercubes with faulty edges |
| title_sort | hamiltonian paths passing through matchings in hypercubes with faulty edges |
| topic | hypercube hamiltonian path matching faulty edges |
| url | https://www.aimspress.com/article/doi/10.3934/math.20241608 |
| work_keys_str_mv | AT shenyangzhao hamiltonianpathspassingthroughmatchingsinhypercubeswithfaultyedges AT fanwang hamiltonianpathspassingthroughmatchingsinhypercubeswithfaultyedges |