Domatic number¶

Assign a graph the largest number of blocks in a vertex partition for which every block is a dominating set.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1708
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Graph Theory, Domination Partitions and Graph Invariants → Mathematics

Core Idea¶

The domatic number \(d(G)\) is the maximum integer \(k\) for which \(V(G)\) has a partition \(\{D_1,\ldots,D_k\}\) and every block \(D_i\) is a dominating set of \(G\).^[1] Each block must meet the closed neighborhood of every vertex, while partition disjointness makes blocks compete for the vertices available in small closed neighborhoods; maximizing the number of such simultaneously dominating blocks turns a feasibility family into a graph invariant.

Its autonomous residual is the maximum cardinality of a vertex partition whose every block independently dominates the whole graph, not merely a minimum dominating-set size or any partition into graph-theoretic special sets. The identity fails when blocks overlap or omit vertices, domination is checked only outside a block under an inconsistent convention, one feasible partition is assumed maximum, minimum and maximum objectives are swapped, isolated vertices are overlooked, or results for total domination or connected domination are imported.

Recognition requires an analyst to state whether graphs are finite, simple, and undirected, verify partition disjointness and exhaustiveness, test domination for every block and vertex, supply both a feasible partition and an upper bound for an exact value, and distinguish the optimization value from the threshold decision problem. Once established, it supports measuring redundant domination, comparing domination and coloring partitions, proving degree bounds, formulating combinatorial optimization problems, studying approximation limits, and evaluating graph classes with special domatic structure without turning those uses into the definition.

How would you explain it like I'm…

Most Guard Teams

Imagine a town of houses joined by paths. A team keeps the town safe if every house has a team member in it or right next door. Now split everybody in town into teams, with each person on exactly one team, so that every team can guard the whole town alone. The domatic number is the most teams you can make.

How Many Full-Coverage Teams

In a graph, dots are connected by lines. A group of dots is 'dominating' if every dot is either in the group or connected to a dot in the group. The Domatic Number asks: if you split all the dots into separate groups with no dot left out and no dot in two groups, what is the largest number of groups you can make where every single group is dominating? Dots with few neighbors limit the answer, because each group needs one of the few dots near them. To know the exact answer, you must show a split that works and also prove no bigger split is possible.

Maximum Dominating-Set Partition

In graph theory, a dominating set is a set of vertices such that every vertex is in the set or adjacent to a member. The Domatic Number d(G) is the maximum number of blocks in a partition of all the vertices where every block is a dominating set. Because blocks cannot share vertices, they compete for the few vertices near low-degree vertices, which caps how many blocks are possible. This is different from the domination number, which asks for the smallest single dominating set. Proving an exact value needs both a valid partition and an upper bound showing you cannot do better, and results about variants like total or connected domination do not automatically carry over.

The Domatic Number d(G) of a graph G is the largest k such that the vertex set V(G) can be partitioned into k blocks, each of which is a dominating set, meaning each block meets the closed neighborhood of every vertex. Partition disjointness forces blocks to compete for vertices in small closed neighborhoods, so a vertex of minimum degree immediately bounds the count. The concept turns a family of feasible partitions into a graph invariant by maximizing. It is not the minimum dominating-set size, nor any partition into special sets; blocks must be disjoint and exhaustive, and every block must dominate every vertex. An exact value requires both a feasible partition and a matching upper bound, and the optimization value must be kept distinct from the threshold decision problem. Conventions matter: finite, simple, undirected graphs; closed-neighborhood domination; attention to isolated vertices; and no importing of results for total or connected domination.

Structural Signature¶

Carrier: a finite undirected graph \(G=(V,E)\), its closed neighborhoods, and partitions of the vertex set \(V\)
Inputs or antecedent state: graph convention, vertex set, adjacency relation, isolated vertices, dominating-set definition, candidate blocks, partition size, minimum degree, and optimization or decision threshold
Constitutive operation: Each block must meet the closed neighborhood of every vertex, while partition disjointness makes blocks compete for the vertices available in small closed neighborhoods; maximizing the number of such simultaneously dominating blocks turns a feasibility family into a graph invariant
Invariant: the blocks are nonempty, pairwise disjoint, collectively exhaustive over \(V(G)\), each block intersects every closed neighborhood, and no partition satisfying those constraints has more blocks
Recognition test: state whether graphs are finite, simple, and undirected, verify partition disjointness and exhaustiveness, test domination for every block and vertex, supply both a feasible partition and an upper bound for an exact value, and distinguish the optimization value from the threshold decision problem
Output or consequence: measuring redundant domination, comparing domination and coloring partitions, proving degree bounds, formulating combinatorial optimization problems, studying approximation limits, and evaluating graph classes with special domatic structure
Failure boundary: blocks overlap or omit vertices, domination is checked only outside a block under an inconsistent convention, one feasible partition is assumed maximum, minimum and maximum objectives are swapped, isolated vertices are overlooked, or results for total domination or connected domination are imported

What It Is Not¶

It is not the whole field of graph theory; many objects in that field do not satisfy its constitutive rule.
It is not its canonical example. For a complete graph \(K_n\), the \(n\) singleton vertex blocks each dominate the graph, so \(d(K_n)=n\). That is an instance, not a definition.
It is not Chromatic Number. Chromatic number minimizes the number of independent-set blocks in a vertex partition. Domatic number maximizes the number of dominating-set blocks; a block can contain adjacent vertices, and every block must reach the entire graph.
It is not an unrestricted metaphor. An isolated vertex forces every dominating set in a partition to contain that vertex, so the domatic number is one; variants using total, connected, independent, or fractional domination change the identity and often the bounds

Scope of Application¶

Domatic number applies when the analyst can specify a finite undirected graph \(G=(V,E)\), its closed neighborhoods, and partitions of the vertex set \(V\) and establish that the blocks are nonempty, pairwise disjoint, collectively exhaustive over \(V(G)\), each block intersects every closed neighborhood, and no partition satisfying those constraints has more blocks. The entry states a mathematical invariant and descriptive complexity results, not an operational network-deployment recipe. Variant names, graph conventions, and complexity assumptions must remain explicit.^[2]

Recognition. state whether graphs are finite, simple, and undirected, verify partition disjointness and exhaustiveness, test domination for every block and vertex, supply both a feasible partition and an upper bound for an exact value, and distinguish the optimization value from the threshold decision problem
Comparison. Compare legitimate instances through graph order, minimum and maximum degree, isolated vertices, domination convention, partition cardinality, graph class, exact value, upper and lower bound, decision threshold, approximation ratio, and computational complexity.
Boundary. An isolated vertex forces every dominating set in a partition to contain that vertex, so the domatic number is one; variants using total, connected, independent, or fractional domination change the identity and often the bounds
Use. Preserve every assumption when using the identity for measuring redundant domination, comparing domination and coloring partitions, proving degree bounds, formulating combinatorial optimization problems, studying approximation limits, and evaluating graph classes with special domatic structure.

Clarity¶

A clear claim names the carrier, governing rule, assumptions, and recognition test. This matters because domatic may be mistaken for domination generally, while number can refer to the optimum value, the associated decision problem, or a variant such as total domatic number. The disciplined statement is that the object counts as Domatic number exactly when the blocks are nonempty, pairwise disjoint, collectively exhaustive over \(V(G)\), each block intersects every closed neighborhood, and no partition satisfying those constraints has more blocks

Identity and measurement remain separate. A proposed partition certifies only a lower bound; exact computation also needs a proof of impossibility above that size, while approximation claims must declare the ratio orientation and complexity assumption. Approximation or noisy evidence may weaken a classification without changing its definition.

Manages Complexity¶

The abstraction compresses complete and bipartite graphs, regular graphs, graphs with isolated vertices, total and connected variants, weighted and fractional generalizations, exact algorithms, approximations, and fixed graph classes into a stable carrier, rule, invariant, and failure boundary. It makes comparison tractable while retaining the variables that control validity.

Compression can hide assumptions. A responsible use therefore declares graph order, minimum and maximum degree, isolated vertices, domination convention, partition cardinality, graph class, exact value, upper and lower bound, decision threshold, approximation ratio, and computational complexity and returns to the full diagnostic whenever a convention or boundary case changes.

Abstract Reasoning¶

Type the carrier. Establish a finite undirected graph \(G=(V,E)\), its closed neighborhoods, and partitions of the vertex set \(V\) and reject examples from a different problem.
Lock the rule. Express that the blocks are nonempty, pairwise disjoint, collectively exhaustive over \(V(G)\), each block intersects every closed neighborhood, and no partition satisfying those constraints has more blocks independently of one notation or implementation.
Derive carefully. Infer measuring redundant domination, comparing domination and coloring partitions, proving degree bounds, formulating combinatorial optimization problems, studying approximation limits, and evaluating graph classes with special domatic structure only under the stated assumptions.
Stress-test. Contrast the legitimate boundary case—An isolated vertex forces every dominating set in a partition to contain that vertex, so the domatic number is one; variants using total, connected, independent, or fractional domination change the identity and often the bounds—with this counterexample: a proper vertex coloring can partition a path into independent color classes even when one color class fails to dominate the path, so a coloring partition is not automatically domatic.

Knowledge Transfer¶

Transfer within graph theory is strong when new cases preserve the same carrier, mechanism, and diagnostic. The move from For a complete graph \(K_n\), the \(n\) singleton vertex blocks each dominate the graph, so \(d(K_n)=n\). to If \(G\) has minimum degree \(\delta\), then \(d(G)\leq\delta+1\), because every dominating block must contain a vertex from the closed neighborhood of a minimum-degree vertex. demonstrates that continuity.^[3]

Outside the domain, only the skeleton—partition one carrier into as many disjoint exhaustive blocks as possible while requiring each block separately to cover every local demand neighborhood—travels automatically. The terms dominating set, domatic partition, closed neighborhood, minimum degree, graph invariant, optimization, decision problem, NP-completeness, and approximation ratio retain domain-specific meanings, so every role and inference must be revalidated.

Examples¶

Canonical¶

For a complete graph \(K_n\), the \(n\) singleton vertex blocks each dominate the graph, so \(d(K_n)=n\). The singleton partition proves the lower bound, and no partition of an (n)-element carrier can have more than (n) nonempty blocks, proving maximality.^[1] It is canonical because the carrier, rule, invariant, and consequence are all inspectable.^[1]

Mapped back: a finite undirected graph \(G=(V,E)\), its closed neighborhoods, and partitions of the vertex set \(V\) → Each block must meet the closed neighborhood of every vertex, while partition disjointness makes blocks compete for the vertices available in small closed neighborhoods; maximizing the number of such simultaneously dominating blocks turns a feasibility family into a graph invariant → the blocks are nonempty, pairwise disjoint, collectively exhaustive over \(V(G)\), each block intersects every closed neighborhood, and no partition satisfying those constraints has more blocks → measuring redundant domination, comparing domination and coloring partitions, proving degree bounds, formulating combinatorial optimization problems, studying approximation limits, and evaluating graph classes with special domatic structure

Applied / In Practice¶

If \(G\) has minimum degree \(\delta\), then \(d(G)\leq\delta+1\), because every dominating block must contain a vertex from the closed neighborhood of a minimum-degree vertex. That neighborhood has only \(\delta+1\) vertices and distinct partition blocks must use distinct representatives there; equality is possible for some graphs but the bound alone does not construct an optimum partition.^[2] It qualifies only after the same diagnostic and failure boundary are checked.^[2]

Mapped back: declared instance → recognition test → boundary check → qualified use

Structural Tensions¶

T1: Exact identity vs. practical recognition. The constitutive condition may be exact while evidence is indirect. Diagnostic: Can the reviewer state both the condition and the warrant?
T2: Canonical form vs. variants. complete and bipartite graphs, regular graphs, graphs with isolated vertices, total and connected variants, weighted and fractional generalizations, exact algorithms, approximations, and fixed graph classes can preserve or change the identity. Diagnostic: Which named role is invariant across the variants?
T3: Compression vs. hidden assumptions. The label is useful only while prerequisites remain visible. Diagnostic: Can each downstream inference be traced to a declared assumption?
T4: Autonomy vs. reduction. The candidate uses broader structures but claims the maximum cardinality of a vertex partition whose every block independently dominates the whole graph, not merely a minimum dominating-set size or any partition into graph-theoretic special sets. Diagnostic: Does that residual still support independent recognition after the parent and neighbors are subtracted?

Structural–Framed Character¶

The entry is structurally mixed but domain-framed. Its portable skeleton is partition one carrier into as many disjoint exhaustive blocks as possible while requiring each block separately to cover every local demand neighborhood; its identity-bearing terms are dominating set, domatic partition, closed neighborhood, minimum degree, graph invariant, optimization, decision problem, NP-completeness, and approximation ratio. Those terms determine admissible objects, evidence, and consequences inside graph theory.

Structural Core vs. Domain Accent¶

The structural core is a carrier governed by Each block must meet the closed neighborhood of every vertex, while partition disjointness makes blocks compete for the vertices available in small closed neighborhoods; maximizing the number of such simultaneously dominating blocks turns a feasibility family into a graph invariant and tested by state whether graphs are finite, simple, and undirected, verify partition disjointness and exhaustiveness, test domination for every block and vertex, supply both a feasible partition and an upper bound for an exact value, and distinguish the optimization value from the threshold decision problem. The domain accent is constitutive rather than decorative, so an analogy that preserves only the skeleton is not another instance of Domatic number.

This entry is a kind of Partition.

Every domatic witness is literally a nonoverlapping and exhaustive partition of the vertex carrier; requiring every block to dominate and maximizing the block count supply the autonomous graph-theoretic specialization. What makes it its own entry is the maximum cardinality of a vertex partition whose every block independently dominates the whole graph, not a minimum dominating-set size or any partition into graph-theoretic special sets.

Relationships to Other Abstractions¶

Current abstraction Domatic number Domain-specific

Parents (1) — outgoing typed relations

Domatic number is a kind of Partition Prime

Every domatic witness is literally a nonoverlapping and exhaustive partition of the vertex carrier; requiring every block to dominate and maximizing the block count supply the autonomous graph-theoretic specialization.

Hierarchy path (1) — routes to 1 parentless root

Domatic number → is a kind of Partition → presupposes Set and Membership

Neighborhood in Abstraction Space¶

Domatic number sits in a crowded region of the domain-specific corpus (16^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Classes & Invariants (40 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With¶

Domination number. Minimizes the size of one dominating set rather than maximizing the number of dominating blocks.
Chromatic number. Minimizes independent blocks, with a different within-block constraint and objective direction.
Achromatic number. Maximizes colors in a complete proper coloring and does not require every color class to dominate under the same definition.
Total domatic number. Requires every vertex, including vertices inside a block, to have a neighbor in that block and therefore excludes self-domination.

References¶

[1] E. J. Cockayne and Stephen T. Hedetniemi, 'Optimal Domination in Graphs,' IEEE Transactions on Circuits and Systems CAS-22(11), 855–857 (1975), DOI 10.1109/TCS.1975.1083994. registry ↩a ↩b ↩c

[2] Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, and Aravind Srinivasan, 'Approximating the Domatic Number,' SIAM Journal on Computing 32(1), 172–195 (2002), DOI 10.1137/S0097539700380754. registry ↩a ↩b ↩c

[3] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979, problem GT3, ISBN 978-0-7167-1045-5. registry ↩