Counting dominating sets in a graph — where a dominating set is a subset of vertices such that every vertex is either in the set or adjacent to it — is known to be #P-complete for general graphs. But the complexity of counting on restricted graph classes is more delicate. Graphs that are simultaneously 3-regular, planar, bipartite, and simple are highly constrained — every vertex has exactly three neighbors, the graph embeds in the plane without crossings, it has no odd cycles, and no parallel edges. Zheng and Meng prove that counting dominating sets remains #P-complete even on this restricted class.
The proof works through gadget construction within their #GDS (General Dominating Set) framework. A gadget is a small graph fragment that, when substituted into a larger construction, simulates a specific computational relationship between its boundary vertices. The art of gadget construction is designing fragments whose local counting properties encode the global counting difficulty of the target problem.
The connection to Holant theory — a framework that unifies constraint satisfaction counting problems through signature functions — provides the machinery. Each vertex's domination constraint becomes a signature, and the graph's structure determines how signatures compose. The #GDS framework organizes these signatures into a hierarchy: dominating sets, total dominating sets, and their generalizations are all instances of (sigma, rho)-sets with different membership conditions.
The structural lesson: extremely constrained graph classes can still carry full computational hardness. The restrictions — regularity, planarity, bipartiteness, simplicity — are all structural, constraining the graph's geometry and connectivity. But #P-completeness is about counting, and counting is sensitive to combinatorial rather than geometric structure. The geometry simplifies; the combinatorics doesn't.