A Graph Bottleneck Inequality

Publication date 15 October 2008

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: For a weighted directed multigraph, let

f_{i j}

be the total weight of spanning converging forests that have vertex

i

in a tree converging to

j

. We prove that

f_{i j} f_{j k} = f_{i k} f_{j j}

if and only if every directed path from

i

to

k

contains

j

(a graph bottleneck equality). Otherwise,

f_{i j} f_{j k} < f_{i k} f_{j j}

(a graph bottleneck inequality). In a companion paper (P. Chebotarev, A new family of graph distances, arXiv preprint arXiv:0810.2717}. Submitted), this inequality underlies, by ensuring the triangle inequality, the construction of a new family of graph distances. This stems from the fact that the graph bottleneck inequality is a multiplicative counterpart of the triangle inequality for proximities.

This page was built for publication: A Graph Bottleneck Inequality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6211248)