Bipartization of graphs

Mateusz Miotk; Jerzy Topp; Paweł Żyliński

doi:10.1007/s00373-019-02068-5

paper

Bipartization of graphs

arXiv:1903.03052 · doi:10.1007/s00373-019-02068-5

Abstract

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 $γ (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.

9 pages, 2 figures