Extremal graphs for inequalities involving domination parameters (Q1567259): Difference between revisions

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). The minimum number of vertices of a dominating set in \(G\) is called the domination number \(\gamma(G)\) of \(G\). A well-known result of O. Ore states that for a graph \(G\) without isolated vertices \(\gamma(G)\leq \lfloor n/2\rfloor\), where \(n\) is the number of vertices of \(G\). In this paper certain six classes of graphs are defined and it is proved that the equality \(\gamma(G)= \lfloor n/2\rfloor\) holds for a connected graph \(G\) if and only if \(G\) belongs to some of those classes. Further the graphs attaining the maximum of a sum of some domination parameters, e.g. \(\gamma(G)+ \gamma(\overline G)\) or \(\gamma(G)+ d(G)\), where \(\overline G\) is the complement of \(G\) and \(d(G)\) is the domatic number of \(G\), are studied.