The domatic number problem
type: Item
instance of: scholarly article
title: The domatic number problem
zbMATH Open document ID: 0799.05032
DOI: 10.1016/0012-365X(94)90151-1
published in: Discrete Mathematics
publication date: 1994-11-24T00:00:00Z
review text: 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.
reviewed by: Zhenhong Liu
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 562654
zbMATH Keywords: dominating set
zbMATH Keywords: domatic number
zbMATH Keywords: NP-complete
zbMATH Keywords: graph operations
author: Gerard Jennhwa Chang
MaRDI profile type: Publication
cites work: On the domatic number of interval graphs
cites work: Dominating sets and domatic number of circular arc graphs
cites work: Q4163262
cites work: A linear algorithm for the domination number of a tree
cites work: Towards a theory of domination in graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4198056
cites work: Q5632603
cites work: Sur le nombre domatique du n-cube et une conjecture de Zelinka. (On the domatic number of the n-cube and a conjecture of Zelinka)
cites work: Q3933018
cites work: The Domatic Number Problem in Interval Graphs
cites work: Q3291034
cites work: R -Domination in Graphs
cites work: Q4028893
cites work: Q3861441
cites work: Q3926622
cites work: Some remarks on domatic numbers of graphs
cites work: Q3947698
cites work: Domatically cocritical graphs
cites work: Q3663328
cites work: Q3313903
cites work: Q3743336
cites work: Regular totally domatically full graphs
description: scientific article; zbMATH DE number 562654