Maximum Size of a Connected Graph with Given Domination Parameters

Let \(G\) be a connected \((p,q)\)-graph. Let \(\gamma_c\) denote the connected domination number of \(G\). In this paper, we prove that \(q\leq \lfloor\frac{p(p-\gamma_c)}{2}\rfloor\) and equality holds if and only if \(G = C_p\) or \(K_p\) or \(K_p – Q\) where \(Q\) is a minimum edge cover of \(K_p\). We obtain similar bounds on \(\gamma_q\) for graphs with given: Total domination number \(\gamma_t\) Clique domination number \(\gamma_k\) Edge domination number \(\gamma ‘\) Connected edge domination number \(\gamma’_{c }\) and for each of these parameters, characterize the class of graphs attaining the corresponding bound.