The graph bottleneck identity

A matrix S=(sij)∈Rn×n is said to determine a transitional measure for a digraph Γ on n vertices if for all i,j,k∈{1,…,n}, the transition inequality sijsjk⩽siksjj holds and reduces to the equality (called the graph bottleneck identity) if and only if every path in Γ from i to k contains j. We show that every positive transitional measure produces a distance by means of a logarithmic transformation. Moreover, the resulting distance d(⋅,⋅) is graph-geodetic, that is, d(i,j)+d(j,k)=d(i,k) holds if and only if every path in Γ connecting i and k contains j. Five types of matrices that determine transitional measures for a digraph are considered, namely, the matrices of path weights, connection reliabilities, route weights, and the weights of in-forests and out-forests.