Jing-Jun Yu

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 $\Delta$, and proposed a conjecture on the sharp bound. In this paper, we develop a probabilistic counting argument based on probability distributions induced by ra...