Total fc-Domatic Partition on Some Classes of Graphs

Abstract

For any positive integer ky the total Jb-dom&tic partition problem is to partition the vertices of a graph into k pairwise disjoint total dominating sets. In this paper, we study the problem for doubly chorda! graphs, cobipartite graphs, chordal bipartite graphs, convex bipartite graphs, bipartite permutation graphs. We show that the total fc-dornatic partition problem is NP-complete for cobipartite graphs. We also show that the total A:-domatic partition problem on doubly chordal graphs is NP-complete, even when k is a fixed integer larger than or equal to 3. For chordal bipartite graphs with weak elimination orderings, we give an alternative algorithm to solve the total fc-domatic partition problem and adapt it to solve the problem in linear time for bipartite permutation graphs and convex bipartite graphs even if T-free forms of the adjacency matrices of the considered graphs are not given. © 2018 Utilitas Mathematica Publishing Incorporated. All rights reserved.