On the number of edges in graphs with a given weakly connected domination number (Q1849997): Difference between revisions

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called a dominating set in \(G\), if it has the property that each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). If, moreover, the set of edges incident with no vertex of \(D\) does not separate the graph \(G\), the set \(D\) is a weakly connected dominating set in \(G\). The minimum cardinality of such a set is the weakly connected domination number \(\gamma_w(G)\) of \(G\). The paper determines \(\left(\begin{smallmatrix} n-d+1\\ 2\end{smallmatrix}\right)\) as the maximum number of edges a graph \(G\) with \(n\) vertices and with \(\gamma_w(G)= d\geq 3\) can have.