Bipartization of Graphs
Mateusz Miotk, Jerzy Topp, Paweł Żyliński · Graphs and Combinatorics · 2019
A dominating set of a graph G is a set $$D\subseteq V_G$$ such that every vertex in $$V_G-D$$ is adjacent to at least one vertex in D, and the domination number $$\gamma (G)$$ of G is the minimum cardinality of a dominating set of G. In this paper we provide a new characterization of bipartite graphs whose domination number is equal to the cardinality of its smaller partite set. Our characterization is based upon a new graph operation.