dominating set

• Wikipedia

In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G

every vertex in the graph is:

• in the dominating set
• or adjacent to a vertex in the dominating set.

Variations

1. Total Dominating Set Problem:

   • In this variant, a total dominating set is considered, where vertices do not cover themselves. It involves finding a subset of vertices in a graph such that every vertex has a neighbor in the set.

flowchart LR
    A((A)) --- B((B))
    B --- C((C))
    C --- D((D))

    classDef selected fill:#f96,stroke:#900,stroke-width:2px;
    classDef unselected fill:#eee,stroke:#555,stroke-width:1px;
    class B,C selected;
    class A,D unselected;

2. Connected Dominating Sets:

   • This variant focuses on finding dominating sets where every vertex not in the set is adjacent to at least one vertex in the dominating set. The dominating set remains connected.

flowchart LR
    v1((v1)) --- v2((v2))
    v2 === v3((v3))
    v3 === v4((v4))
    v4 --- v5((v5))

    classDef selected fill:#69b3a2,stroke:#0f5132,stroke-width:2px;
    classDef unselected fill:#eee,stroke:#555,stroke-width:1px;
    class v2,v3,v4 selected;
    class v1,v5 unselected;

3. Power Domination:

   • Power domination is another variant where a minimum-size vertex set is determined such that each vertex is either in the set or adjacent to at least one vertex in the set.

     1. Direct observation: Every vertex in ‭ $S$ ‬ and all its immediate neighbors ‭ $N[S]$ ‬‭‬‭‬‭‬ become observed.
     2. Propagation: If an observed vertex has exactly one unobserved neighbor, that unobserved neighbor becomes observed. This propagates iteratively until no further vertices can be added.

eventually monitor the graph.

flowchart LR
    A((A)) --- B((B))
    B --- C((C))
    B --- E((E))
    C --- D((D))

    classDef pmu fill:#f96,stroke:#900,stroke-width:2px;
    classDef direct fill:#ffe0b2,stroke:#f57c00,stroke-width:2px;
    classDef propagated fill:#b3e5fc,stroke:#0288d1,stroke-width:2px;
    class B pmu;
    class A,C,E direct;
    class D propagated;

4. Paired-Domination:

   • Paired-domination is a variant where two dominating sets are sought, and the sum of their sizes along with their intersection is minimized.

   • A set ‭$S\subseteq V$‬‭‬ is a Paired Dominating Set if:

     1. ‭ $S$ ‬ is a standard dominating set (‭ $N[S]=V$ ‬‭‬‭‬‭‬‭‬).
     2. The induced subgraph ‭ $G[S]$ ‬‭‬‭‬‭‬ contains a perfect matching (a 1-factor). That is, ‭ $|S|$ ‬{}‭‬‭‬{} is even, and ‭ $S$ ‬ can be partitioned into disjoint pairs of mutually adjacent vertices.

flowchart TD
    1((1)) === 2((2))
    2 --- 3((3))
    3 --- 4((4))
    4 === 5((5))
    5 --- 6((6))
    6 --- 1

    classDef pairA fill:#ce93d8,stroke:#6a1b9a,stroke-width:2px;
    classDef pairB fill:#90caf9,stroke:#1565c0,stroke-width:2px;
    classDef unselected fill:#eee,stroke:#555,stroke-width:1px;
    class 1,2 pairA;
    class 4,5 pairB;
    class 3,6 unselected;

Videos

• https://youtu.be/0jKRpZch81I

Example of Dominating Set Problems

• Roman Domination
• Double Roman Domination