Counting geodesic paths in graphs

Martin Knor, Jelena Sedlar, Riste Škrekovski, Xiao-Dong Zhang

arXivarxiv/2604.04907Apr 6, 2026math.COscore 0

A geodesic is a shortest path which connects a pair of vertices of a graph G. In this paper we define the geodesic subpath number gpn(G) of a graph G as the number of geodesics in G. The number of subtrees and subpaths are already studied in literature, but they are both large quantities. Hence, the geodesic subpath number which is related to these quantities but smaller than both, seems worthy of investigation. We first consider extremal graphs with respect to the geodesic subpath number among all connected graphs on n vertices. This number is minimized by the so called geodetic graphs,…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.04907
curl -X POST /api/v1/records/arxiv/2604.04907/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.04907/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'