Totally Disjoint Diametral Paths August 10, 2026

Arthur M. Farley, Tınaz Ekim · 2026

Read Totally Disjoint Diametral Paths August 10, 2026 by Arthur M. Farley, Tınaz Ekim (2026) 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-2606-27451.txt.

Description

Farley and Ekim study paths that cross a graph the long way without touching each other at all. A diametral path joins two vertices at maximum possible distance, the graph's diameter. Totally disjoint such paths share no vertices, not even endpoints, modelling independent worst-case routes through a network, in a graph theory paper published in 2026. Deciding whether a graph holds a given number of them is proven NP-complete, so no efficient general algorithm is expected.

A linear-time algorithm handles a subclass of maximal outerplanar graphs called two-paths. Threshold graphs admit a polynomial-time algorithm, and proper interval graphs get a structural bound on the count. Extremal graphs achieving given numbers of disjoint diametral paths with the fewest possible edges are characterised. Hardness and tractability are mapped side by side. Network designers learn where redundant long-haul routing is computable.

Catalog record

CREATORArthur M. Farley, Tınaz Ekim
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27451

Browse the full library · About the Tower of Babel