Distance in Graphs: Trees

Abstract

The distance of a vertex $u$ in a connected graph $G$ is defined by ${\sigma }_G(u):=\sum _{v\in V(G)}d(u,v)$, and the distance of $G$ is given by $\sigma (G)=\frac{1}{2}\sum _{u\in V(G)}\sigma (u)(=\sum _{\{u,v\}\subseteq V(G)}d(u,v)$. Thus, the average distance between vertices in a connected graph $G$ of order $n$ is $\frac{\sigma (G)}{(\genfrac{}{}{0ex}{}{n}{2})}$. These graph invariants have been studied for the past fifty years. Here, we discuss some known properties and present a few new results, together with several open problems. We focus on trees.