Signed and Minus Total Domination on Subclasses of Bipartite Graphs

Abstract

In this paper, we study the signed and minus total domination problems for two subclasses of bipartite graphs: biconvex bipartite graphs and planar bipartite graphs. We present a unified method to solve the signed and minus total domination problems for biconvex bipartite graphs in \(O(n + m)\) time. We also prove that the decision problem corresponding to the signed (respectively, minus) total domination problem is NP-complete for planar bipartite graphs of maximum degree \(3\) (respectively, maximum degree \(4\)).