The domatic number problem
A dominating set of a graph \(G=(V,E)\) is a subset \(D\) of \(V\) such that every vertex not in \(D\) is adjacent to some vertex in \(D\). The domatic number of \(G\) is the maximum positive integer \(k\) such that \(V\) can be partioned into \(k\) pairwise disjoint dominating sets. It was proved that the problem of determining the domatic number of a graph is NP-complete for general graphs. This paper investigates the domatic number of graphs which are obtained from small graphs by performing graph operations, such as union, join and the Cartesian product.
scientific article; zbMATH DE number 562654
scientific article