Hamiltonian connectivity of some base-cobase graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916813566115840 |
|---|---|
| author | Martínez-Sandoval, Leonardo Knauer, Kolja |
| author_facet | Martínez-Sandoval, Leonardo Knauer, Kolja |
| contents | There has been wide interest in understanding which properties of base graphs of matroids extend to base-cobase graphs of matroids. A significant result of Naddef and Pulleyblank (1984) shows that the $1$-skeleton of any $(0,1)$-polytope is either a hypercube, or Hamiltonian-connected, i.e. there is a Hamiltonian path connecting any two vertices. In particular, this is true for base graphs of matroids. A natural question raised by Farber, Richter, and Shank (1985) is whether this extends to base-cobase graphs.
First, we use the polytopal approach to show Hamiltonian connectivity of base-cobase graphs of series-parallel extensions of lattice path matroids. On the other hand, we show that this method extends to only very special classes related to identically self-dual matroids. Second, we show that base-cobase graphs of wheels and whirls are Hamiltonian connected. Last, we show that the regular matroid $R_{10}$ yields a negative answer to the question of Farber, Richter, and Shank. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15049 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hamiltonian connectivity of some base-cobase graphs Martínez-Sandoval, Leonardo Knauer, Kolja Combinatorics Discrete Mathematics There has been wide interest in understanding which properties of base graphs of matroids extend to base-cobase graphs of matroids. A significant result of Naddef and Pulleyblank (1984) shows that the $1$-skeleton of any $(0,1)$-polytope is either a hypercube, or Hamiltonian-connected, i.e. there is a Hamiltonian path connecting any two vertices. In particular, this is true for base graphs of matroids. A natural question raised by Farber, Richter, and Shank (1985) is whether this extends to base-cobase graphs. First, we use the polytopal approach to show Hamiltonian connectivity of base-cobase graphs of series-parallel extensions of lattice path matroids. On the other hand, we show that this method extends to only very special classes related to identically self-dual matroids. Second, we show that base-cobase graphs of wheels and whirls are Hamiltonian connected. Last, we show that the regular matroid $R_{10}$ yields a negative answer to the question of Farber, Richter, and Shank. |
| title | Hamiltonian connectivity of some base-cobase graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2506.15049 |