The Maximum Number of Shortest Paths in Graphs
Benjamini and Tzalik obtained an upper bound on the number of shortest paths between two vertices at distance $t$ in a multigraph of maximum degree at most $Δ$, and proposed a conjecture on the sharp bound. In this paper, we develop a probabilistic counting argument based on probability distributions induced by random walks from the two endpoints. This approach yields a sharp bound for multigraphs and confirms their conjecture. We further determine the exact maximum for simple graphs and thus answer another question of Benjamini and Tzalik. We also investigate the equality cases, describing…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.02334
curl -X POST /api/v1/records/arxiv/2609.02334/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.02334/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'