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

CREATORDibyayan Chakraborty, Florent Foucaud
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-10828

Browse the full library · About the Tower of Babel