Further results regarding the sum of domination number and average eccentricity

摘要

The average eccentricity of a graph G, denoted by ecc(G), is the mean value of eccentricities of all vertices of G. Let Dn, i be the n-vertex tree obtained from a path Pn−1=v1v2⋯vn−1 by attaching a pendent vertex to vi. In [13], it was shown that the maximum value for the sum of domination number and average eccentricity among n-vertex (connected) graphs is attained by Dn, 3 when n≡0(mod3), and attained by the path Pn when n¬≡0(mod3). In this paper, we will further determine the second maximum value for the sum of domination number and average eccentricity among n-vertex (connected) graphs. It is interesting that the graphs attaining that second maximum value have three cases, which is Dn, 6 when n≡0(mod3), Dn, 3 when n≡1(mod3), and Tn when n≡2(mod3), where Tn is the n-vertex tree obtained from a path Pn−2=v1v2⋯vn−2 by attaching a pendent vertex to v3, and a pendent vertex to vn−4.