Distances and volumina for graphs Academic Article uri icon


  • It has long been realized that connected graphs have some sort of geometric structure, in that there is a natural distance function (or metric), namely, the shortest-path distance function. In fact, there are several other natural yet intrinsic distance functions, including: the resistance distance, correspondent "square-rooted" distance functions, and a so-called "quasi-Euclidean" distance function. Some of these distance functions are introduced here, and some are noted not only to satisfy the usual triangle inequality but also other relations such as the "tetrahedron inequality". Granted some (intrinsic) distance function, there are different consequent graph-invariants. Here attention is directed to a sequence of graph invariants which may be interpreted as: the sum of a power of the distances between pairs of vertices of G, the sum of a power of the "areas" between triples of vertices of G, the sum of a power of the "volumes" between quartets of vertices of G, etc. The Cayley-Menger formula for n-volumes in Euclidean space is taken as the defining relation for so-called "n-volumina" in terms of graph distances, and several theorems are here established for the volumina-sum invariants (when the mentioned power is 2).

published proceedings


author list (cited authors)

  • Klein, D. J., & Zhu, H. Y.

citation count

  • 36

complete list of authors

  • Klein, DJ||Zhu, HY

publication date

  • April 1998