The graph bottleneck identity

Abstract

A matrix $S=(s_{ij})\in {\mathbb{R}}^{n\times n}$ is said to determine a \emph{transitional measure} for a digraph $G$ on $n$ vertices if for all $i,j,k\in \{1,\dot{.}.,n\},$ the \emph{transition inequality} $s_{ij}{s}_{jk}\le s_{ik}{s}_{jj}$ holds and reduces to the equality (called the \emph{graph bottleneck identity}) if and only if every path in $G$ 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(\cdot ,\cdot )$ is \emph{graph-geodetic}, that is, $d(i,j)+d(j,k)=d(i,k)$ holds if and only if every path in $G$ 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. The results obtained have undirected counterparts. In [P. Chebotarev, A class of graph-geodetic distances generalizing the shortest-path and the resistance distances, Discrete Appl. Math., URL http://dx.doi.org/10.1016/j.dam.2010.11.017] the present approach is used to fill the gap between the shortest path distance and the resistance distance.

12 pages, 18 references. Advances in Applied Mathematics

References in corpus (1)

• Forest matrices around the Laplacian matrix

Cited by in corpus (9)

• The Walk Distances in Graphs
• Similarities on Graphs: Kernels versus Proximity Measures
• Studying new classes of graph metrics
• Nonlocal PageRank
• Selection of Centrality Measures Using Self-Consistency and Bridge Axioms
• Simple expressions for the long walk distance
• How to choose the most appropriate centrality measure? A decision tree approach
• A topological interpretation of the walk distances
• Protometrics