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\). 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.

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.

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.

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

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.

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.

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.

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