Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2503.09087 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913732396843008 |
|---|---|
| author | Luo, Ye |
| author_facet | Luo, Ye |
| contents | Recently, the study of circuits and cycles within the homology classes of graphs has attracted considerable research interest. However, the detection and counting of shorter circuits in homology classes, especially the shortest ones, remain underexplored. This paper aims to fill this gap by solving the problem of detecting and counting the shortest cycles in homology classes, leveraging the concept of direction-consistent circuits and extending classical results on Eulerian circuits such as Hierholzer's algorithm and the BEST theorem. As an application, we propose the one-carrier transportation routing problem and relate it to a circuit detection problem in graph homology. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_09087 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Shortest Circuits in Homology Classes of Graphs Luo, Ye Combinatorics 05C38, 05C45, 05C50, 90C27 Recently, the study of circuits and cycles within the homology classes of graphs has attracted considerable research interest. However, the detection and counting of shorter circuits in homology classes, especially the shortest ones, remain underexplored. This paper aims to fill this gap by solving the problem of detecting and counting the shortest cycles in homology classes, leveraging the concept of direction-consistent circuits and extending classical results on Eulerian circuits such as Hierholzer's algorithm and the BEST theorem. As an application, we propose the one-carrier transportation routing problem and relate it to a circuit detection problem in graph homology. |
| title | Shortest Circuits in Homology Classes of Graphs |
| topic | Combinatorics 05C38, 05C45, 05C50, 90C27 |
| url | https://arxiv.org/abs/2503.09087 |