The domatic number of regular graphs

Peter Dankelmann, Neil Calkin

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


The domatic number of a graph G is the maximum number of dominating sets into which the vertex set of G can be partitioned. We show that the domatic number of a random r-regular graph is almost surely at most r, and that for 3-regular random graphs, the domatic number is almost surely equal to 3. We also give a lower bound on the domatic number of a graph in terms of order, minimum degree and maximum degree. As a corollary, we obtain the result that the domatic number of an r-regular graph is at least (r + 1)/(3ln(r + 1)).

Original languageEnglish
Pages (from-to)247-255
Number of pages9
JournalArs Combinatoria
Publication statusPublished - Oct 2004
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics


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

Cite this