Gallai-type theorems and domination parameters (Q1356464)

If \(\gamma(G)\) and \(\Delta(G)\) denote the domination number and maximum degree (respectively) of a graph \(G\) of order \(n\), then it is known that \(\gamma(G)\leq n-\Delta(G)\). Those connected bipartite graphs which achieve this bound are characterised, and two conditions are furnished in the general case which are necessary if \(\gamma(G)+ \Delta(G)=n\), and sufficient to achieve \(n-1\leq \gamma(G)+ \Delta(G)\leq n\). Similar relations are investigated for the independent domination number, irredundance number, and upper irredundance number.