Domatic number¶

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

Version: v2 · 2026-08-30 · History
Domain-specific #: 1708
Origin domain: graph theory
Subdomain: domination partitions and graph invariants

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.

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.

The proposed strict upward parent is prime: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. The edge is proposal-only and points to a frozen prior-baseline Prime.

The entry does not collapse into the parent because 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 A thematic neighbor is declined whenever it does not literally subsume that rule.

The prospective workspace queue contains one strict upward edge to prime:partition. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Domatic number Domain-specific

Parents (1) — more general patterns this builds on

Domatic number is a kind of Partition Prime

The proposed strict upward parent is prime:partition.

Hierarchy path (1) — routes to 1 parentless root

Domatic number → Partition → Set and Membership

Neighborhood in Abstraction Space¶

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

Family — Graph Connectivity & Network Measures (31 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

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 ↩