Mathematics – Combinatorics
Scientific paper
2010-03-20
Advances in Applied Mathematics. 47 (2011), No.3, P.403-413
Mathematics
Combinatorics
12 pages, 18 references. Advances in Applied Mathematics
Scientific paper
10.1016/j.aam.2010.11.001
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,\...,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.
No associations
LandOfFree
The graph bottleneck identity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The graph bottleneck identity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The graph bottleneck identity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-127171