Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
Dibyayan Chakraborty, Florent Foucaud · 2025
Read Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations by Dibyayan Chakraborty, Florent Foucaud (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10828.txt.
Description
Dibyayan Chakraborty and Florent Foucaud present a 2025 study in graph theory, centered on a measure called strong isometric path complexity. The measure asks how the shortest paths in a graph can be covered by a few paths that share one end point. The authors test which kinds of graphs keep that number bounded.
They show that graphs free of certain asymptotic minors have bounded complexity, and they give exact bounds for graphs built from small pieces. Some graph classes fail the test, while monoholed graphs pass it. They also check which graph operations keep the bound, such as fixed powers and line graphs.
Catalog record
| CREATOR | Dibyayan Chakraborty, Florent Foucaud |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-10828