PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.)
Vol. 56(70), pp. 18--22 (1994)
On a graph invariant related to the sum of all distances in a graph
A. Dobrynin and I. GutmanInstitute of Mathematics, Russian Academy of Sciences, Siberian Branch, Novosibirsk 630090, Russia and Prirodno-matematicki fakultet, Kragujevac, Yugoslavia
Abstract: Let $W(G)$ be the sum of distances between all pairs of vertices of a graph $G$. For an edge $e$ of $G$, connecting the vertices $u$ and $v$, the number $n_u(e)$ counts the vertices of $G$ that lie closer to $u$ than to $v$. In this paper we consider the graph invariant $W^\ast(G)=\sum_e n_u(e)n_v(e)$, defined for any connected graph $G$. According to a long-known result in the theory of graph distances, if $G$ is a tree then $W^\ast(G)=W(G)$. We establish a number of properties of the graph invariant $W^\ast$.
Classification (MSC2000): 05C12
Full text of the article:
Electronic fulltext finalized on: 1 Nov 2001. This page was last modified: 16 Nov 2001.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts