Average distance and domination number (Q1377614)

The average distance \(\mu(G)\) of a graph \(G\) with \(n\) vertices is obtained from the sum of distances \(d_G(x,y)\) for all ordered pairs \(x\), \(y\) of vertices of \(G\) by dividing by \(n(n-1)\). By \(\gamma(G)\) the domination number of \(G\) is denoted, i.e. the minimum number of vertices of a dominating set in \(G\). (A subset \(D\) of the vertex set of \(G\) is called dominating, if each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\).) The main results are formulated in two theorems which give upper bounds for \(\mu(G)\) in terms of \(n\) and \(\gamma(G)\). The first theorem holds for graphs with \(\gamma(G)\leq n/3\), the second for graphs with \(\gamma(G)\geq n/3\).