Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.17236 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912166490144768 |
|---|---|
| author | Zhu, Hongyi Deng, Qingying |
| author_facet | Zhu, Hongyi Deng, Qingying |
| contents | We investigate the combined occurrence of edge faults and vertex faults in the burnt pancake graph (\( BP_n \)). In this paper, we prove that \( BP_n - F \), where \( F \) includes pairs of end-vertices of matching edges and fault-tolerant edges, contains a Hamiltonian cycle when \( |F| \leq n-2 \) and a Hamiltonian path when \( |F| \leq n-3 \). This establishes that \( BP_n \) is \((n-2)\)-hybrid fault Hamiltonian and \((n-3)\)-hybrid fault Hamiltonian connected for \( n \geq 3 \). These results are demonstrated to be optimal under the given conditions, with all bounds shown to be tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17236 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hamiltonian Properties of Hybrid-Faulty Burnt Pancake Graphs Zhu, Hongyi Deng, Qingying Combinatorics We investigate the combined occurrence of edge faults and vertex faults in the burnt pancake graph (\( BP_n \)). In this paper, we prove that \( BP_n - F \), where \( F \) includes pairs of end-vertices of matching edges and fault-tolerant edges, contains a Hamiltonian cycle when \( |F| \leq n-2 \) and a Hamiltonian path when \( |F| \leq n-3 \). This establishes that \( BP_n \) is \((n-2)\)-hybrid fault Hamiltonian and \((n-3)\)-hybrid fault Hamiltonian connected for \( n \geq 3 \). These results are demonstrated to be optimal under the given conditions, with all bounds shown to be tight. |
| title | Hamiltonian Properties of Hybrid-Faulty Burnt Pancake Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.17236 |