There are no excess one digraphs

Slobodan Filipovski [email protected] ORCID: 0000-0002-7286-4954, Arnau Messegué [email protected] ORCID: 0000-0002-7425-7592, Josep M. Miret [email protected] ORCID: 0000-0003-4631-4294, James Tuite [email protected] ORCID: 0000-0003-2604-7491 · 2025

Read There are no excess one digraphs by Slobodan Filipovski [email protected] ORCID: 0000-0002-7286-4954, Arnau Messegué [email protected] ORCID: 0000-0002-7425-7592, Josep M. Miret [email protected] ORCID: 0000-0003-4631-4294, James Tuite [email protected] ORCID: 0000-0003-2604-7491 (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-2512-02827.txt.

Description

Slobodan Filipovski and three co-authors settle a question about directed graphs with nearly unique short routes. A digraph is called k-geodetic when any two vertices are joined by at most one walk of length up to k. Graphs close to the limits of this property are counted by an excess value.

The title states the result plainly: there are no excess one digraphs. The proof rules out a whole borderline family that might have existed. Nonexistence results prune the search space for network designs built on unique routing. A clean no can save years: no team need hunt for a graph that math says can not be built at all.

Catalog record

CREATORSlobodan Filipovski [email protected] ORCID: 0000-0002-7286-4954, Arnau Messegué [email protected] ORCID: 0000-0002-7425-7592, Josep M. Miret [email protected] ORCID: 0000-0003-4631-4294, James Tuite [email protected] ORCID: 0000-0003-2604-7491
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02827

Browse the full library · About the Tower of Babel