Maximum size of a connected graph with given domination parameters (Q2761000)

Four domination parameters of graphs are considered. A subset \(S\) of the vertex set \(V\) of a graph \(G\) is called dominating, if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). If a dominating set \(S\) induces a connected subgraphs \(\langle S\rangle\) of \(G\), it is called connected dominating. If moreover \(\langle S\rangle\) is a clique of \(G\), then \(S\) is called clique dominating. If each vertex of \(G\) is adjacent to a vertex of \(S\), then \(S\) is called total dominating. If \(S\) is a subset of the edge set \(E\) of \(G\) such that each edge of \(G\) either is in \(S\), or has a common end vertex with an edge of \(S\), then \(S\) is called an edge dominating set in \(G\). If moreover \(S\) induces a connected subgraph of \(G\), it is called connected edge dominating. The minimum cardinalities of such sets are subsequently the domination number \(\gamma(G)\), the connected domination number \(\gamma_c(G)\), the clique domination number \(\gamma_k(G)\), the total domination number \(\gamma_t(G)\), the edge domination number \(\gamma'(G)\) and the connected edge domination number \(\gamma_c'(G)\) of \(G\). For each of those parameters the paper shows an upper bound for the number \(q\) of edges of \(G\) in terms of that parameter and the number \(p\) of vertices of \(G\). Always the conditions for attaining this bound exactly are stated.