Partitioning the vertices of a graph into two total dominating sets

Abstract

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every self-complementary graph with minimum degree at least two has such a partition.

Mathematics Subject Classification (2010): 05C69.

Keywords: Total domination, vertex partitions, dominating sets, self-complementary graphs