On AutoGraphiX conjecture regarding domination number and average eccentricity


Li-Dan Pei, Xiang-Feng Pan, Jing Tian, Gui-Qin Peng




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 ⊆ V(G) is a dominating set of a graph G if NG(v)∩ S , ∅ for any vertex v ∈ V(G) S. The domination number γ(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 γ(T) − ecc(T) for an n-vertex tree T