Note on Hamiltonicity of basis graphs of even delta-matroids
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911104274268160 |
|---|---|
| author | Kim, Donggyu Oum, Sang-il |
| author_facet | Kim, Donggyu Oum, Sang-il |
| contents | We show that the basis graph of an even delta-matroid is Hamiltonian if it has more than two vertices. More strongly, we prove that for two distinct edges $e$ and $f$ sharing a common end, it has a Hamiltonian cycle using $e$ and avoiding $f$ unless it has at most two vertices or it is a cycle of length at most four. We also prove that if the basis graph is not a hypercube graph, then each vertex belongs to cycles of every length $\ell\ge 3$, and each edge belongs to cycles of every length $\ell \ge 4$. For the last theorem, we provide two proofs, one of which uses the result of Naddef (1984) on polytopes and the result of Chepoi (2007) on basis graphs of even delta-matroids, and the other is a direct proof using various properties of even delta-matroids. Our theorems generalize the analogous results for matroids by Holzmann and Harary (1972) and Bondy and Ingleton (1976). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_05772 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Note on Hamiltonicity of basis graphs of even delta-matroids Kim, Donggyu Oum, Sang-il Combinatorics 05B35, 05C38, 05C45 We show that the basis graph of an even delta-matroid is Hamiltonian if it has more than two vertices. More strongly, we prove that for two distinct edges $e$ and $f$ sharing a common end, it has a Hamiltonian cycle using $e$ and avoiding $f$ unless it has at most two vertices or it is a cycle of length at most four. We also prove that if the basis graph is not a hypercube graph, then each vertex belongs to cycles of every length $\ell\ge 3$, and each edge belongs to cycles of every length $\ell \ge 4$. For the last theorem, we provide two proofs, one of which uses the result of Naddef (1984) on polytopes and the result of Chepoi (2007) on basis graphs of even delta-matroids, and the other is a direct proof using various properties of even delta-matroids. Our theorems generalize the analogous results for matroids by Holzmann and Harary (1972) and Bondy and Ingleton (1976). |
| title | Note on Hamiltonicity of basis graphs of even delta-matroids |
| topic | Combinatorics 05B35, 05C38, 05C45 |
| url | https://arxiv.org/abs/2308.05772 |