2026/07/21 by Holger Spakowski
Computer Science · #cs.CC #cs.DM
The domatic number dom(G) of a graph G is the maximum number of dominating sets in a partition of its vertex set. A graph is domatically critical if deleting any edge lowers its domatic number. We determine the complexity of recognizing domatically critical graphs both when the domatic number is prescribed and when it is unrestricted. The problems DomCrit1 and DomCrit2 are polynomial-time decidable; in particular, DomCrit2 consists precisely of the nonempty disjoint unions of nontrivial stars. In contrast, for every fixed integer k >= 3, the problem DomCritk is DP-complete under polynomial-time many-one reductions. The hardness proof at target value three uses a switch construction that reduces from edge-minimal 3-uncolorability and controls the effect of deleting every edge of the constructed graph. Clique addition then lifts the target-three result to every larger fixed target value. For the unrestricted recognition problem, we prove DP-hardness and membership in Theta2p.