The domatic numbers of factors of graphs

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review


The maximum cardinality of a partition of the vertex set of a graph G into dominating sets is the domatic number of G, denoted d(G). We consider Nordhaus-Gaddum type results involving the domatic number of a graph, where a Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. Thereafter we investigate the upper bounds on the sum and product of the domatic numbers d(G1), d(G2) and d(G3) where G1⊕G2⊕G3 = Kn. We show that the upper bound on the sum is n + 2, while the maximum value of the product is ⌊n/3⌋3 for n ≥ 57.

Original languageEnglish
Pages (from-to)161-173
Number of pages13
JournalArs Combinatoria
Publication statusPublished - Jul 2000
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'The domatic numbers of factors of graphs'. Together they form a unique fingerprint.

Cite this