Further Connectivity Results on Plane Spanning Path Reconfiguration
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911938056814592 |
|---|---|
| author | Boucard, Valentino da Fonseca, Guilherme D. Rivier, Bastien |
| author_facet | Boucard, Valentino da Fonseca, Guilherme D. Rivier, Bastien |
| contents | Given a finite set $ S $ of points, we consider the following reconfiguration graph. The vertices are the plane spanning paths of $ S $ and there is an edge between two vertices if the two corresponding paths differ by two edges (one removed, one added). Since 2007, this graph is conjectured to be connected but no proof has been found. In this paper, we prove several results to support the conjecture. Mainly, we show that if all but one point of $ S $ are in convex position, then the graph is connected with diameter at most $ 2 | S | $ and that for $ | S | \geq 3 $ every connected component has at least $ 3 $ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_00244 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Further Connectivity Results on Plane Spanning Path Reconfiguration Boucard, Valentino da Fonseca, Guilherme D. Rivier, Bastien Computational Geometry Discrete Mathematics Given a finite set $ S $ of points, we consider the following reconfiguration graph. The vertices are the plane spanning paths of $ S $ and there is an edge between two vertices if the two corresponding paths differ by two edges (one removed, one added). Since 2007, this graph is conjectured to be connected but no proof has been found. In this paper, we prove several results to support the conjecture. Mainly, we show that if all but one point of $ S $ are in convex position, then the graph is connected with diameter at most $ 2 | S | $ and that for $ | S | \geq 3 $ every connected component has at least $ 3 $ vertices. |
| title | Further Connectivity Results on Plane Spanning Path Reconfiguration |
| topic | Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2407.00244 |