Certified dominating set

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 ${\displaystyle D}$ of officials and a set ${\displaystyle 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.¹

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

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

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

For any graph ${\displaystyle G}$ of order ${\displaystyle n}$:¹

• The vertex set ${\displaystyle V}$ is always a certified dominating set, so ${\displaystyle 1\leq \gamma _{\text{cer}}(G)\leq n}$.
• ${\displaystyle \gamma _{\text{cer}}(G)\neq n-1}$ for any graph.
• Every support vertex of ${\displaystyle G}$ belongs to every certified dominating set.
• ${\displaystyle \gamma _{\text{cer}}(G)=1}$ if and only if ${\displaystyle G}$ has order at least three and contains a universal vertex.
• If ${\displaystyle G_{1},G_{2},\ldots ,G_{k}}$ are the connected components of ${\displaystyle G}$, then ${\displaystyle \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 ${\displaystyle P_{n}}$:
  • ${\displaystyle \gamma _{\text{cer}}(P_{n})=1}$ if ${\displaystyle n=1}$ or ${\displaystyle n=3}$
  • ${\displaystyle \gamma _{\text{cer}}(P_{n})=2}$ if ${\displaystyle n=2}$
  • ${\displaystyle \gamma _{\text{cer}}(P_{n})=4}$ if ${\displaystyle n=4}$
  • ${\displaystyle \gamma _{\text{cer}}(P_{n})=\lceil n/3\rceil }$ otherwise
• For the cycle ${\displaystyle C_{n}}$ with ${\displaystyle n\geq 3}$:
  • ${\displaystyle \gamma _{\text{cer}}(C_{n})=\lceil n/3\rceil }$
• For the complete graph ${\displaystyle K_{n}}$:
  • ${\displaystyle \gamma _{\text{cer}}(K_{n})=1}$ if ${\displaystyle n=1}$ or ${\displaystyle n\geq 3}$
  • ${\displaystyle \gamma _{\text{cer}}(K_{n})=2}$ if ${\displaystyle n=2}$
• For the complete bipartite graph ${\displaystyle K_{m,n}}$ with ${\displaystyle 1\leq m\leq n}$:
  • ${\displaystyle \gamma _{\text{cer}}(K_{m,n})=1}$ if ${\displaystyle m=1}$ and ${\displaystyle n>1}$
  • ${\displaystyle \gamma _{\text{cer}}(K_{m,n})=2}$ otherwise
• For the wheel graph ${\displaystyle W_{n}}$:
  • ${\displaystyle \gamma _{\text{cer}}(W_{n})=1}$

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

${\displaystyle \gamma _{\text{cer}}(G)\leq \gamma (G)+|S_{1}(G)|}$

where ${\displaystyle \gamma (G)}$ is the domination number and ${\displaystyle 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, ${\displaystyle \gamma _{\text{cer}}(G)\leq 2\gamma (G)}$. Additionally, if the strong support vertices of ${\displaystyle G}$ are adjacent to ${\displaystyle k}$ leaves in total, then ${\displaystyle \gamma _{\text{cer}}(G)\leq n-k}$.¹

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

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

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

A graph ${\displaystyle G}$ is called ${\displaystyle \gamma \gamma _{\text{cer}}}$-perfect if ${\displaystyle \gamma (H)=\gamma _{\text{cer}}(H)}$ for every induced connected subgraph ${\displaystyle H\neq K_{2}}$ of ${\displaystyle G}$. A graph is ${\displaystyle \gamma \gamma _{\text{cer}}}$-perfect if and only if it is ${\displaystyle P_{4}}$-free.²

A graph ${\displaystyle G}$ of order ${\displaystyle n}$ satisfies ${\displaystyle \gamma _{\text{cer}}(G)=n}$ if and only if ${\displaystyle 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 ${\displaystyle H\circ K_{1}}$ by adding a new vertex and joining it to one support vertex of ${\displaystyle H\circ K_{1}}$. A graph ${\displaystyle G}$ of order ${\displaystyle n\geq 3}$ satisfies ${\displaystyle \gamma _{\text{cer}}(G)=n-2}$ if and only if ${\displaystyle G}$ is ${\displaystyle C_{3}}$, ${\displaystyle C_{4}}$, or a diadem graph, possibly combined with the corona of a graph and isolated vertices.¹

Adding an edge to a connected graph cannot increase the certified domination number: ${\displaystyle \gamma _{\text{cer}}(G+e)\leq \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 ${\displaystyle v}$ to a graph ${\displaystyle G}$ satisfies ${\displaystyle \gamma _{\text{cer}}(G+v)\leq \gamma _{\text{cer}}(G)+1}$.¹

For a graph ${\displaystyle G}$ of order ${\displaystyle n\geq 5}$ with complement ${\displaystyle {\overline {G}}}$:¹

${\displaystyle \gamma _{\text{cer}}(G)+\gamma _{\text{cer}}({\overline {G}})\leq n+2}$

${\displaystyle \gamma _{\text{cer}}(G)\cdot \gamma _{\text{cer}}({\overline {G}})\leq 2n}$

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

If ${\displaystyle \min\{\delta (G),\delta ({\overline {G}})\}\geq 2}$, stronger bounds hold:¹

${\displaystyle \gamma _{\text{cer}}(G)+\gamma _{\text{cer}}({\overline {G}})\leq \left\lfloor {\frac {n}{2}}\right\rfloor +2}$

${\displaystyle \gamma _{\text{cer}}(G)\cdot \gamma _{\text{cer}}({\overline {G}})\leq n}$

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 ${\displaystyle \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 ${\displaystyle \gamma (G)\neq \gamma _{\text{cer}}(G)}$ for a given graph ${\displaystyle G}$ is also NP-hard, even when ${\displaystyle G}$ has only one weak support vertex. This is shown by a reduction from 3SAT.³