Totally Disjoint Diametral Paths
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.27451
curl -X POST /api/v1/records/arxiv/2606.27451/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.27451/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'