Skip to content
DraconiticResearch
Search Sources API
186,541 studies31 sourcesUpdated 40 min ago
PreprintarXiv licencearXiv

The Maximum Number of Shortest Paths in Graphs

  • Jing Yu
  • Jie-Xiang Zhu
Open at sourcePDFDOICite

Abstract

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 the structure of the subgraph formed by shortest paths between x and y and giving tight examples.

Related

  1. Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
    Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung +3
    HALPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsHALarXiv
  2. The game chromatic number of generalized Mycielski graphs of paths and cycles
    Yushuang Mou, Qiang Sun, Chao Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The maximum size of intersecting k-graphs with covering number k
    Peter Frankl, Jian Wang, Yaoran Yang +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Maximum number of spanning trees in bipartite graphs with a given diameter
    Shaohan Xu, Ivan Damnjanović, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The maximum number of edges in minimal matching covered graphs
    Xiaoling He
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yu2026maximum,
  title = {{The Maximum Number of Shortest Paths in Graphs}},
  author = {Jing Yu and Jie-Xiang Zhu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02334},
  eprint = {2609.02334},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02334},
}
RIS
TY  - UNPB
TI  - The Maximum Number of Shortest Paths in Graphs
AU  - Jing Yu
AU  - Jie-Xiang Zhu
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.02334
UR  - https://arxiv.org/abs/2609.02334
AB  - 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 the structure of the subgraph formed by shortest paths between x and y and giving tight examples.
ER  -