Zagreb Indices of Graphs with Given Connected Domination Number

The first and second Zagreb indices of a graph \(G\) are \(M₁(G) = ∑ᵥ^{}d(v)²\) and \(M₂(G) = ∑uv ∈ 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 \(γ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₁\) and of \(M₂\) is always attained by a tree with exactly \(n - k\) leaves. We determine the minimum of \(M₁\) for every pair \((n,k)\) together with all extremal graphs, and the minimum of \(M₂\) for \(k ∈ \{ 1,2,n - 3,n - 2\}\). On the upper side, we determine the maximum of \(M₁\) and \(M₂\) for \(k ∈ \{ 1,2,n - 2\}\), and we prove the sharp bound \(M₁(G) ≤ (n - k + 1)(n - k)² + 4(k - 1)\) for all connected graphs with \(γc(G) = k ≥ 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₁\) and for \(M₂\) without the minimum-degree restriction; we state this as a conjecture. For trees we obtain sharp lower and upper bounds on \(M₁\) in terms of the order and the number of leaves.