The average distance of spanning trees in terms of independence number

Abstract

Let $G$ be a connected graph with vertex set $V(G)$, and denote by $d_G(u,v)$ the distance from $u$ to $v$ in $G$, for any $u,v\in V(G)$. The average distance of an $n$-vertex connected graph $G$, denoted by $\mu (G)$, is defined to be the average of all distances between all pairs of vertices in $G$, i.e., $\mu (G)={\left(\genfrac{}{}{0ex}{}{n}{2}\right)}^{-1}{\sum }_{\{u,v\}\subset V(G)}{d}_G(u,v)$. The problem of finding a spanning tree of minimum average distance is known to be NP-hard, so establishing an upper bound for the minimum average distance among all spanning trees is of particular interest. Mukwembi (J. Graph Theory, 2014) showed that if $G$ is a connected graph of order $n$ with independence number $\alpha$, where $n>2\alpha -1$, then $G$ has a spanning tree $T$ such that $\mu (T)\le \alpha +2$. In this paper, we first improve the upper bound to $\mu (T)<\alpha +1$ for $\alpha \ge 1$, and then we find the bound could be further improved when $\alpha$ becomes larger, so a better upper bound \[ μ(T) < \left\{ \begin{array}{ll} α+1 & \hbox{if } 1\leα\le 6,\\ α+\frac12+\frac{4(α-1)}{α^2} & \hbox{if } α\ge 7, \end{array} \right. \] is established later. In the end, we give a remark to indicate our new upper bound is best possible in the sense of asymptotics (when $n$ and $\alpha$ are large enough).