Maximum number of edges in connected graphs with a given domination number (Q1174141): Difference between revisions

A dominating set in a graph is a subset \(U\) of its vertices such that each vertex not in \(U\) has a neighbour in \(U\). The domination number is the minimum size of a dominating set. The paper under review shows that a graph with \(n\) vertices, domination number \(d\) (where \(3\leq d\leq n/2)\) and no isolated vertices has at most \(n-d+1\choose 2\) edges. The graphs for which this bound is tight are also characterized. The proof is based on work of \textit{Y. Usami} [``Minimum number of edges in graphs that are both \(P_ 2\)- and \(P_ i\)-connected'', Discrete Math. 44, 195-199 (1983; Zbl 0503.05038)]. The corresponding bound and related characterization for graphs with isolated vertices is due to Vizing.