Disproof of a Conjecture About Average Steiner Distance

Abstract

Given a connected graph $G$ and a subset $S$ of vertices, the Steiner distance of $S$ in $G$ is the minimum number of edges in a tree in $G$ that contains all of $S$. Given a positive integer $m$, let ${\mu }_m(G)$ denote the average Steiner distance over all sets $S$ of $m$ vertices in $G$. In particular, ${\mu }_2(G)$ is just the average distance of $G$, often denoted by $\mu (G)$. Dankelmann, Oellermann, and Swart $[1]$ conjectured that if $G$ is a connected graph of order $n$ and $3\le m\le n$, then $\frac{{\mu }_m(G)}{\mu (G)}\ge 3(\frac{m-1}{m+1})$. In this note, we disprove their conjecture by showing that

$$\underset{m\to \mathrm{\infty }}{lim}inf\{\frac{{\mu }_m(G)}{\mu (G)}:G\text{ is connected and }n(G)\ge m\}=2.$$