Let \(G=(V(G),E(G))\) be a graph. A set \(D\subseteq V(G)\) is a distance k-dominating set of G if for every vertex \(u\in V(G)\setminus D\), \(d_{G}(u,v)\leq k\) for some vertex \(v\in D\), where k is a positive integer. The distance k-domination number \(\gamma_{k}(G)\) of G is the minimum cardinality among all distance k-dominating sets of G. The first Zagreb index of G is defined as \(M_{1}=\sum_{u\in V(G)}d^{2}(u)\) and the second Zagreb index of G is \(M_{2}=\sum_{uv\in E(G)}d(u)d(v)\). In this paper, we obtain the upper bounds for the Zagreb indices of n-vertex trees with given distance k-domination number and characterize the extremal trees, which generalize the results of Borovićanin and Furtula (Appl. Math. Comput. 276:208–218, 2016). What is worth mentioning, for an n-vertex tree T, is that a sharp upper bound on the distance k-domination number \(\gamma _{k}(T)\) is determined.
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 ≠ 0 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.
The domination number of a nonempty graph is the minimum cardinality among all subsets such that . The bondage number of a graph is the smallest number of edges whose removal from results in a graph with larger domination number. The exact value of for and the bounds of for are determined.