Domination in partitioned graphs with minimum degree two (Q870974): Difference between revisions

Let \(V_1\) and \(V_2\) be a partition of the vertex set in a graph \(G\). For \(i=1,2\), let \(\gamma_i\) denote the least number of vertices needed in \(G\) to dominate \(V_i\). It is known that if \(G\) has order \(n\) and minimum degree two, then \(\gamma_1+\gamma_2\leq 2n/3\). The contribution of this paper is the complete characterization of those graphs of order \(n\) which are edge minimal with respect to satisfying the conditions of connected, minimum degree at least two, and \(\gamma_1+\gamma_2=2n/3\).