Shortest Circuits in Homology Classes of Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |