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
| CREATOR | Arthur M. Farley, Tınaz Ekim |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27451