2023/11/16 by Itaï Benjamini, Benjamini, Itai, Elad Tzalik +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2311.10014
It is proved that the number of shortest paths between two vertices of distance t in a graph with degrees bounded by Δ is at most 2 ⋅ (\fracΔ2)t. This improves upon the naïve Δ(Δ-1) t-1 bound.