Zagreb Indices of Graphs with Given Connected Domination Number

The first and second Zagreb indices of a graph \(G\) are \(M_{1}(G) = \sum_{v}^{}d(v)^{2}\) and \(M_{2}(G) = \sum_{uv \in E(G)}^{}d(u)d(v)\). We investigate hw these indices behave on the class of connected graphs of order \(n\) whose connected domination number equals a prescribed value \(k\). Our starting point is the identity \(\gamma_{c}(G) = n - ml(G)\), where \(ml(G)\) is the maximum number of leaves of a spanning tree of \(G\). It shows that the minimum of \(M_{1}\) and of \(M_{2}\) is always attained by a tree with exactly \(n - k\) leaves. We determine the minimum of \(M_{1}\) for every pair \((n,k)\) together with all extremal graphs, and the minimum of \(M_{2}\) for \(k \in \{ 1,2,n - 3,n - 2\}\). On the upper side, we determine the maximum of \(M_{1}\) and \(M_{2}\) for \(k \in \{ 1,2,n - 2\}\), and we prove the sharp bound \(M_{1}(G) \leq (n - k + 1)(n - k)^{2} + 4(k - 1)\) for all connected graphs with \(\gamma_{c}(G) = k \geq 3\) and no pendant vertex. The bound is attained by an explicit graph, which a computer search over all connected graphs of order at most \(10\) identifies as the extremal graph for \(M_{1}\) and for \(M_{2}\) without the minimum-degree restriction; we state this as a conjecture. For trees we obtain sharp lower and upper bounds on \(M_{1}\) in terms of the order and the number of leaves.