Reconfigurations of Plane Caterpillars and Paths
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912067020128256 |
|---|---|
| author | Antić, Todor Quintero, Guillermo Gamboa Glišić, Jelena |
| author_facet | Antić, Todor Quintero, Guillermo Gamboa Glišić, Jelena |
| contents | Let $S$ be a point set in the plane, $\mathcal{P}(S)$ and $\mathcal{C}(S)$ sets of all plane spanning paths and caterpillars on $S$. We study reconfiguration operations on $\mathcal{P}(S)$ and $\mathcal{C}(S)$. In particular, we prove that all of the commonly studied reconfigurations on plane spanning trees still yield connected reconfiguration graphs for caterpillars when $S$ is in convex position. If $S$ is in general position, we show that the rotation, compatible flip and flip graphs of $\mathcal{C}(S)$ are connected while the slide graph is disconnected. For paths, we prove the existence of a connected component of size at least $2^{n-1}$ and that no component of size at most $7$ can exist in the flip graph on $\mathcal{P}(S)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_07419 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconfigurations of Plane Caterpillars and Paths Antić, Todor Quintero, Guillermo Gamboa Glišić, Jelena Combinatorics Computational Geometry 05C10 (Primary) 68R10 (Secondary) G.2 Let $S$ be a point set in the plane, $\mathcal{P}(S)$ and $\mathcal{C}(S)$ sets of all plane spanning paths and caterpillars on $S$. We study reconfiguration operations on $\mathcal{P}(S)$ and $\mathcal{C}(S)$. In particular, we prove that all of the commonly studied reconfigurations on plane spanning trees still yield connected reconfiguration graphs for caterpillars when $S$ is in convex position. If $S$ is in general position, we show that the rotation, compatible flip and flip graphs of $\mathcal{C}(S)$ are connected while the slide graph is disconnected. For paths, we prove the existence of a connected component of size at least $2^{n-1}$ and that no component of size at most $7$ can exist in the flip graph on $\mathcal{P}(S)$. |
| title | Reconfigurations of Plane Caterpillars and Paths |
| topic | Combinatorics Computational Geometry 05C10 (Primary) 68R10 (Secondary) G.2 |
| url | https://arxiv.org/abs/2410.07419 |