Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.05404 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912632509825024 |
|---|---|
| author | Milanič, Martin Mitrović, Đorđe |
| author_facet | Milanič, Martin Mitrović, Đorđe |
| contents | It was shown by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2022 that every induced $2$-edge path in a vertex-transitive graph closes to an induced cycle. Similar results were obtained for 3-edge paths closing to cycles in edge-transitive graphs, where the cycle can be assumed to be induced if the path is induced. Motivated by these results, we consider the following problem: For a given class of graphs, determine all integers $\ell\geq 0$ such that for every graph in the class, every path of length at most $\ell$ closes to a cycle. We also consider the variant of the problem for induced paths closing to induced cycles. We completely solve these problems for the classes of (finite) vertex-transitive graphs, edge-transitive graphs, and edge-transitive graphs that are not stars. For all but one case of a negative answer, we provide infinite families of connected counterexamples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05404 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Closing paths to cycles in symmetric graphs Milanič, Martin Mitrović, Đorđe Combinatorics 05C38, 05E18 It was shown by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2022 that every induced $2$-edge path in a vertex-transitive graph closes to an induced cycle. Similar results were obtained for 3-edge paths closing to cycles in edge-transitive graphs, where the cycle can be assumed to be induced if the path is induced. Motivated by these results, we consider the following problem: For a given class of graphs, determine all integers $\ell\geq 0$ such that for every graph in the class, every path of length at most $\ell$ closes to a cycle. We also consider the variant of the problem for induced paths closing to induced cycles. We completely solve these problems for the classes of (finite) vertex-transitive graphs, edge-transitive graphs, and edge-transitive graphs that are not stars. For all but one case of a negative answer, we provide infinite families of connected counterexamples. |
| title | Closing paths to cycles in symmetric graphs |
| topic | Combinatorics 05C38, 05E18 |
| url | https://arxiv.org/abs/2510.05404 |