On the number of edges in graphs with a given connected domination number (Q1972141)

The paper is devoted to the problem of finding the maximum number of edges in a graph with given connected domination number. A connected dominating set \(V\) of a graph \(G\) is a set of vertices that is dominating and the graph induced by \(V\) is connected. The connected domination number of \(G\) is the size of its smallest connected dominating set. The main result of the paper is a characterization of graphs with given connected domination number. It is proved that for a connected graph \(G\) with \(n\) vertices and connected domination number \(d\) the number of edges in \(G\) is at most \(\binom{n-d+1} {2}+(d-1)\). Moreover extremal graphs achieving this bound are characterized.