Certified dominating set

A graph with a minimum certified dominating set colored. Red vertices are illuminated, while blue vertices are shadowed.

In graph theory, a certified dominating set of a graph is a type of dominating set in which every vertex in the set has either zero or at least two neighbours outside the set. The concept was introduced by Dettlaff, Lemańska, Topp, Ziemann, and Żyliński in 2018.

The concept models a scenario involving officials and civilians in a social network. Given a set $D$ of officials and a set $W$ of civilians, each civilian must be served by some official, and whenever an official serves a civilian, there must be at least one other civilian who can observe the official, acting as a witness to prevent potential abuse. The certified domination number represents the minimum number of officials needed to guarantee such a service.

Definition

Let $G=(V,E)$ be a graph. A dominating set $D\subseteq V$ is called a certified dominating set if for every vertex $v\in D$, the number of neighbours of $v$ in $V\setminus D$ is either zero or at least two. Equivalently, no vertex in $D$ has exactly one neighbour outside $D$.

The certified domination number of $G$, denoted ${\gamma }_{\text{cer}}(G)$, is the minimum cardinality of a certified dominating set in $G$. A certified dominating set of minimum cardinality is called a ${\gamma }_{\text{cer}}$-set.

The vertices of $D$ can be classified based on their neighbours in $V\setminus D$. A vertex in $D$ with no neighbours in $V\setminus D$ is called shadowed, a vertex in $D$ with exactly one neighbour in $V\setminus D$ is called half-shadowed, and a vertex in $D$ with at least two neighbours in $V\setminus D$ is called illuminated. A dominating set is certified if and only if it contains no half-shadowed vertices.

Properties and examples

For any graph $G$ of order $n$:

• The vertex set $V$ is always a certified dominating set, so $1\le {\gamma }_{\text{cer}}(G)\le n$.
• ${\gamma }_{\text{cer}}(G)\ne n-1$ for any graph.
• Every support vertex of $G$ belongs to every certified dominating set.
• ${\gamma }_{\text{cer}}(G)=1$ if and only if $G$ has order at least three and contains a universal vertex.
• If $G_1,G_2,\dots ,G_k$ are the connected components of $G$, then ${\gamma }_{\text{cer}}(G)=\sum _{i=1}^k{\gamma }_{\text{cer}}(G_i)$.

The certified domination number is known exactly for several families of graphs:

• For the path $P_n$:
  • ${\gamma }_{\text{cer}}(P_n)=1$ if $n=1$ or $n=3$
  • ${\gamma }_{\text{cer}}(P_n)=2$ if $n=2$
  • ${\gamma }_{\text{cer}}(P_n)=4$ if $n=4$
  • ${\gamma }_{\text{cer}}(P_n)=\lceil n/3\rceil$ otherwise
• For the cycle $C_n$ with $n\ge 3$:
  • ${\gamma }_{\text{cer}}(C_n)=\lceil n/3\rceil$
• For the complete graph $K_n$:
  • ${\gamma }_{\text{cer}}(K_n)=1$ if $n=1$ or $n\ge 3$
  • ${\gamma }_{\text{cer}}(K_n)=2$ if $n=2$
• For the complete bipartite graph $K_{m,n}$ with $1\le m\le n$:
  • ${\gamma }_{\text{cer}}(K_{m,n})=1$ if $m=1$ and $n>1$
  • ${\gamma }_{\text{cer}}(K_{m,n})=2$ otherwise
• For the wheel graph $W_n$:
  • ${\gamma }_{\text{cer}}(W_n)=1$

Bounds and relation to domination number

Since every certified dominating set is a dominating set, $\gamma (G)\le {\gamma }_{\text{cer}}(G)$ for all graphs $G$. For a connected graph $G$, the certified domination number satisfies:

${\gamma }_{\text{cer}}(G)\le \gamma (G)+|S_1(G)|$

where $\gamma (G)$ is the domination number and $S_1(G)$ is the set of weak support vertices (support vertices adjacent to exactly one leaf). This bound is sharp, as equality holds for the corona of any graph without isolated vertices. As a consequence, ${\gamma }_{\text{cer}}(G)\le 2\gamma (G)$. Additionally, if the strong support vertices of $G$ are adjacent to $k$ leaves in total, then ${\gamma }_{\text{cer}}(G)\le n-k$.

Equality ${\gamma }_{\text{cer}}(G)=\gamma (G)$ holds in several cases:

• If $G$ has no weak support vertex (in particular, if $\delta (G)\ge 2$), then ${\gamma }_{\text{cer}}(G)=\gamma (G)$.
• If $G$ has a unique minimum dominating set, then ${\gamma }_{\text{cer}}(G)=\gamma (G)$.
• If $\gamma (G-v)\ge \gamma (G)$ for every vertex $v$ belonging to at least one $\gamma$-set of $G$, then ${\gamma }_{\text{cer}}(G)=\gamma (G)$.
• If $G$ is a connected $P4$-free graph and $G\ne K_2$, then ${\gamma }_{\text{cer}}(G)=\gamma (G)$.

More generally, for a connected graph $G$ of order at least three, ${\gamma }_{\text{cer}}(G)=\gamma (G)$ if and only if $G$ has a $\gamma$-set $D$ such that every vertex in $D$ has at least two neighbours in $V\setminus D$.

A graph $G$ is called $\gamma {\gamma }_{\text{cer}}$-perfect if $\gamma (H)={\gamma }_{\text{cer}}(H)$ for every induced connected subgraph $H\ne K_2$ of $G$. A graph is $\gamma {\gamma }_{\text{cer}}$-perfect if and only if it is $P_4$-free.

Graphs with large certified domination number

The minimum certified dominating set for the graph shown consists of the entire vertex set

A graph $G$ of order $n$ satisfies ${\gamma }_{\text{cer}}(G)=n$ if and only if $G$ is the complement of a complete graph, the corona of a graph, or the disjoint union of both.

A diadem graph is a graph obtained from the corona $H\circ K_1$ by adding a new vertex and joining it to one support vertex of $H\circ K_1$. A graph $G$ of order $n\ge 3$ satisfies ${\gamma }_{\text{cer}}(G)=n-2$ if and only if $G$ is $C_3$, $C_4$, or a diadem graph, possibly combined with the corona of a graph and isolated vertices.

Effects of graph modifications

Adding an edge to a connected graph cannot increase the certified domination number: ${\gamma }_{\text{cer}}(G+e)\le {\gamma }_{\text{cer}}(G)$. However, both deleting an edge from a graph and adding an edge to a disconnected graph may arbitrarily increase the certified domination number.

Adding a leaf vertex may arbitrarily increase the certified domination number, but adding a non-leaf vertex $v$ to a graph $G$ satisfies ${\gamma }_{\text{cer}}(G+v)\le {\gamma }_{\text{cer}}(G)+1$.

Nordhaus–Gaddum type inequalities

For a graph $G$ of order $n\ge 5$ with complement $\bar{G}$:

${\gamma }_{\text{cer}}(G)+{\gamma }_{\text{cer}}(\bar{G})\le n+2$

${\gamma }_{\text{cer}}(G)\cdot {\gamma }_{\text{cer}}(\bar{G})\le 2n$

Equality holds in both inequalities simultaneously if and only if $G$ or $\bar{G}$ is the corona of some graph.

If $\min \{\delta (G),\delta (\bar{G})\}\ge 2$, stronger bounds hold:

${\gamma }_{\text{cer}}(G)+{\gamma }_{\text{cer}}(\bar{G})\le \lfloor \frac{n}{2}\rfloor +2$

${\gamma }_{\text{cer}}(G)\cdot {\gamma }_{\text{cer}}(\bar{G})\le n$

Computational complexity

The problem of determining the certified domination number is NP-hard even for bipartite planar subcubic graphs with no leaves. This follows from the equality ${\gamma }_{\text{cer}}(G)=\gamma (G)$ for graphs with no weak support vertices and the known NP-hardness of the domination problem in such graph classes.

Determining whether $\gamma (G)\ne {\gamma }_{\text{cer}}(G)$ for a given graph $G$ is also NP-hard, even when $G$ has only one weak support vertex. This is shown by a reduction from 3SAT.

See also

• Dominating set
• Corona product
• Nordhaus-Gaddum theorem