{"id":"arxiv/2606.27451","url":"https://arxiv.org/abs/2606.27451","tags":["math.CO","cs.DM"],"score":0,"title":"Totally Disjoint Diametral Paths","domain":"math.CO","source":"arxiv","authors":["Tınaz Ekim","Arthur Farley"],"reviews":0,"subject":"math.CO","summary":"In this paper, we study totally disjoint diametral paths in simple connected graphs. A diametral path in a graph is a shortest path that connects two vertices whose mutual distance is equal to the diameter of the graph. Totally disjoint paths are paths that have no vertices in common, including their end vertices. We show that the problem of deciding whether a graph $G$ has $k$ totally disjoint diametral paths is NP-complete. We consider restricted classes of graphs for which the problem of determining the maximum size of a set of totally disjoint diametral paths is readily solved. We then…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-25","reactions":{}}