On AutoGraphiX conjecture regarding domination number and average eccentricity

Abstract

The eccentricity of a vertex is the maximal distance from it to another vertex and the average eccentricity $ecc(G)$ of a graph $G$ is the mean value of eccentricities of all vertices of $G$. A set $S\subseteq V(G)$ is a dominating set of a graph $G$ if $N_{G}(v)\cap S\ne \emptyset$ for any vertex $v\in V(G)\setminus S$.
The domination number $\gamma(G)$ of $G$ is the minimum cardinality of all dominating sets of $G$. In this paper, we correct an AutoGraphiX conjecture regarding the domination number and average eccentricity, and present a proof of the revised conjecture. In addition, we establish an upper bound on $\gamma(T)-ecc(T)$ for an $n$-vertex tree $T$.