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 \leq m \leq n\), then \(\frac{\mu_m(G)}{\mu(G)} \geq 3(\frac{m-1}{m+1})\). In this note, we disprove their conjecture by showing that

\[\lim_{m \to \infty} inf \{ \frac{\mu_m(G)}{\mu(G)} :G \text{ is connected and $n(G)\geq m$} \} = 2.\]