In graph theory, a domatic partition of a graph <math>G = (V,E)</math> is a partition of <math>V</math> into disjoint sets <math>V_1</math>, <math>V_2</math>,... ,<math>V_K</math> such that each Vi is a dominating set for G.

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • In graph theory, a domatic partition of a graph <math>G = (V,E)</math> is a partition of <math>V</math> into disjoint sets <math>V_1</math>, <math>V_2</math>,... ,<math>V_K</math> such that each Vi is a dominating set for G. The figure on the rights shows a domatic partition of a graph; here the dominating set <math>V_1</math> consists of the yellow vertices, <math>V_2</math> consists of the green vertices, and <math>V_3</math> consists of the blue vertices. The domatic number is the maximum size of a domatic partition, that is, the maximum number of disjoint dominating sets. The graph in the figure has domatic number 3. It is easy to see that the domatic number is at least 3 because we have presented a domatic partition of size 3. To see that the domatic number is at most 3, we first review a simple upper bound.
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • In graph theory, a domatic partition of a graph <math>G = (V,E)</math> is a partition of <math>V</math> into disjoint sets <math>V_1</math>, <math>V_2</math>,... ,<math>V_K</math> such that each Vi is a dominating set for G.
rdfs:label
  • Domatic number
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of
is owl:sameAs of