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.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. \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, \ldots, 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 \geq 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 \geq 3 \gamma_{\text{cer}}(K_n) = 2 if n = 2 For the complete bipartite graph K_{m,n} with 1 \leq m \leq 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 Equality \gamma_{\text{cer}}(G) = \gamma(G) holds in several cases: If G has no weak support vertex (in particular, if \delta(G) \geq 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) \geq \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 P_4 -free graph and G \neq 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 \neq K_2 of G . A graph is \gamma\gamma_{\text{cer}} -perfect if and only if it is P_4 -free.
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 \geq 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. 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) \neq \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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1336138378 under CC BY-SA 4.0; modifications have been made.