On Domination Number and Distance in Graphs

Abstract

A vertex set $S$ of a graph $G$ is a \emph{dominating set} if each vertex of $G$ either belongs to $S$ or is adjacent to a vertex in $S$. The \emph{domination number} $\gamma (G)$ of $G$ is the minimum cardinality of $S$ as $S$ varies over all dominating sets of $G$. It is known that $\gamma (G)\ge \frac{1}{3}(diam(G)+1)$, where $diam(G)$ denotes the diameter of $G$. Define $C_r$ as the largest constant such that $\gamma (G)\ge C_r{\sum }_{1\le i<j\le r}d(x_i,x_j)$ for any $r$ vertices of an arbitrary connected graph $G$; then $C_2=\frac{1}{3}$ in this view. The main result of this paper is that $C_r=\frac{1}{r(r-1)}$ for $r\ge 3$. It immediately follows that $\gamma (G)\ge \mu (G)=\frac{1}{n(n-1)}W(G)$, where $\mu (G)$ and $W(G)$ are respectively the average distance and the Wiener index of $G$ of order $n$. As an application of our main result, we prove a conjecture of DeLaViña et al.\;that $\gamma (G)\ge \frac{1}{2}(ec{c}_G(B)+1)$, where $ec{c}_G(B)$ denotes the eccentricity of the boundary of an arbitrary connected graph $G$.

5 pages, 2 figures