Certified dominating set

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Certified dominating set (short, easy version)

Definition
- In a graph G = (V, E), a dominating set D is a group of vertices that together touch every vertex outside D. A certified dominating set is a special kind of dominating set: for every vertex v in D, the number of neighbors of v that lie outside D is either 0 or at least 2. In other words, no vertex in D has exactly one neighbor outside D.

Intuition
- Think of D as officials and V \ D as civilians. Every civilian must be served (covered) by some official, and whenever an official serves someone, there should be at least one other civilian who can observe the official to prevent abuse. The “outside D” condition captures this observer idea.

Certified domination number
- The smallest possible size of a certified dominating set in G is called the certified domination number, γcer(G). A certified dominating set of that smallest size is a γcer-set.

Vertex types inside a certified dominating set
- Inside D, vertices can be:
- Shadowed: has no neighbors outside D.
- Half-shadowed: has exactly one neighbor outside D.
- Illuminated: has at least two neighbors outside D.
- A dominating set is certified exactly when it has no half-shadowed vertices.

Key relationships and bounds
- Every certified dominating set is a regular dominating set, so γ(G) ≤ γcer(G).
- The certified domination number is not larger than twice the ordinary domination number: γcer(G) ≤ 2 · γ(G).
- If many “strong” support vertices are attached to leaves, there are stronger bounds like γcer(G) ≤ n − k (where n is the number of vertices and k counts certain leaves).

When do we have equality?
- Sometimes γcer(G) = γ(G). This happens, for example, if there is a smallest dominating set where every vertex has at least two neighbors outside the set.
- The concept of γcer-perfect graphs and other special graph families describe other exact cases, but these ideas are more advanced.

What if the graph is large or simple changes?
- Adding an edge never increases γcer(G); it can stay the same or go down.
- Removing an edge or adding a separate component can make γcer(G) larger, sometimes by a lot.
- Adding a leaf can cause a big jump in γcer(G); adding a non-leaf vertex v changes γcer by at most 1.

Computational complexity
- Finding γcer(G) is hard in general (NP-hard). It remains hard even for certain restricted kinds of graphs, like bipartite planar graphs with degree at most 3 and no leaves.
- Deciding whether γ(G) ≠ γcer(G) is also NP-hard, even for graphs with only a single weak support vertex.

Summary
- A certified dominating set covers all vertices while ensuring every official either has no outside neighbors or has at least two outsiders to observe, preventing single-point abuse. The smallest such set is γcer(G), and it sits between the ordinary domination number γ(G) and 2·γ(G), with several known cases and many computational challenges.