# Chapter 65. Dominating Sets

# Chapter 65. Dominating Sets

A dominating set is a set of vertices such that every vertex of the graph either belongs to the set or is adjacent to a vertex in the set. Dominating sets model coverage, influence, monitoring, control, and facility placement. They appear in communication networks, sensor systems, social networks, distributed computing, and optimization. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Dominating_set?utm_source=chatgpt.com))

Dominating sets differ fundamentally from vertex covers and independent sets. A vertex cover controls edges. A dominating set controls vertices through adjacency.

The central question is:

> How few vertices are needed to influence or monitor the entire graph?

This chapter develops the basic theory of domination.

## 65.1 Definition

Let

$$
G=(V,E)
$$

be a graph.

A subset

$$
D \subseteq V
$$

is called a dominating set if every vertex outside \(D\) is adjacent to at least one vertex in \(D\).

Equivalently:

$$
\forall v \in V \setminus D,
\quad
\exists u \in D
$$

such that:

$$
uv \in E.
$$

Thus every vertex is either:

| Situation | Meaning |
|---|---|
| In \(D\) | Directly selected |
| Adjacent to \(D\) | Dominated |

For example, in the path:

$$
v_1-v_2-v_3-v_4-v_5,
$$

the set:

$$
D=\{v_2,v_4\}
$$

is dominating.

Every vertex either belongs to \(D\) or neighbors one of these vertices.

## 65.2 Domination Number

A dominating set is minimum if it has smallest possible size.

The domination number of \(G\) is denoted by:

$$
\gamma(G).
$$

Thus:

$$
\gamma(G) =
\min\{|D| : D \text{ is a dominating set}\}.
$$

The minimum dominating set problem asks for a dominating set of minimum size.

This problem is NP-complete. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Dominating_set?utm_source=chatgpt.com))

## 65.3 Trivial Dominating Sets

Some dominating sets are immediate.

### Entire Vertex Set

The set:

$$
V
$$

is always dominating.

### Single Dominating Vertex

If some vertex is adjacent to every other vertex, then that single vertex forms a dominating set.

Such a vertex is called universal.

For example, the center of a star graph dominates the entire graph.

## 65.4 Dominating Sets in Standard Graphs

### Complete Graphs

In the complete graph:

$$
K_n,
$$

every vertex is adjacent to all others.

Thus:

$$
\gamma(K_n)=1.
$$

### Star Graphs

For the star:

$$
K_{1,n},
$$

the center dominates all vertices.

Hence:

$$
\gamma(K_{1,n})=1.
$$

### Paths

For the path graph:

$$
P_n,
$$

$$
\gamma(P_n) =
\left\lceil \frac{n}{3} \right\rceil.
$$

### Cycles

For the cycle graph:

$$
C_n,
$$

$$
\gamma(C_n) =
\left\lceil \frac{n}{3} \right\rceil.
$$

Optimal domination selects approximately every third vertex.

## 65.5 Closed Neighborhoods

The closed neighborhood of a vertex \(v\) is:

$$
N[v] =
\{v\}
\cup
N(v).
$$

Thus the closed neighborhood includes the vertex itself together with all neighbors.

A set \(D\) is dominating if:

$$
\bigcup_{v \in D} N[v] =
V.
$$

\bigcup_{v \in D} N[v]=V

This formulation is often useful in proofs and algorithms.

## 65.6 Minimal and Minimum Dominating Sets

As usual, minimal and minimum are different concepts.

| Term | Meaning |
|---|---|
| Minimal dominating set | No vertex removable |
| Minimum dominating set | Smallest possible size |

Every minimum dominating set is minimal.

The converse need not hold.

### Example

A dominating set may contain unnecessary redundancy while still being locally irreducible.

## 65.7 Independent Dominating Sets

A dominating set may also be independent.

An independent dominating set satisfies:

| Property | Meaning |
|---|---|
| Independent | No adjacent selected vertices |
| Dominating | Every vertex controlled |

These sets combine sparsity with coverage.

### Example

In a path:

$$
v_1-v_2-v_3-v_4-v_5,
$$

the set:

$$
\{v_2,v_5\}
$$

is independent and dominating.

## 65.8 Maximal Independent Sets

Every maximal independent set is dominating.

### Proof

Let:

$$
I
$$

be maximal independent.

Suppose some vertex \(v\) is neither in \(I\) nor adjacent to any vertex of \(I\).

Then adding \(v\) to \(I\) preserves independence, contradicting maximality.

Therefore every vertex outside \(I\) must neighbor \(I\).

Hence \(I\) is dominating.

This important observation links domination with independence theory.

## 65.9 Domination and Independence

Let:

| Parameter | Meaning |
|---|---|
| \(\gamma(G)\) | Domination number |
| \(i(G)\) | Minimum independent domination number |
| \(\alpha(G)\) | Independence number |

These parameters satisfy many inequalities.

For example:

$$
\gamma(G)\le i(G)\le \alpha(G).
$$

The first inequality holds because independent dominating sets are special dominating sets.

The second holds because independent dominating sets are independent.

## 65.10 Dominating Set Algorithms

### Brute Force

Test all subsets:

$$
2^{|V|}
$$

possibilities.

This becomes infeasible for large graphs.

### Greedy Algorithms

Greedy domination algorithms repeatedly select vertices covering many uncovered vertices.

These methods are fast but may not produce optimal solutions.

### Approximation Algorithms

The minimum dominating set problem admits logarithmic-factor approximations.

The problem is closely related to set cover.

## 65.11 Domination and Set Cover

Dominating set can be formulated as a set-cover problem.

For each vertex \(v\), define the closed neighborhood:

$$
N[v].
$$

The goal is to choose as few closed neighborhoods as possible whose union equals \(V\).

Thus domination is a graph-theoretic version of set covering.

This connection explains why dominating set is computationally difficult.

## 65.12 Domination in Trees

Trees admit efficient domination algorithms.

Dynamic programming methods consider whether a vertex is:

| State | Meaning |
|---|---|
| Selected | Dominates itself and neighbors |
| Dominated by parent | Already covered |
| Requires domination | Must be covered by child |

Combining subtree solutions yields linear-time algorithms.

Trees therefore form one of the most tractable domination classes.

## 65.13 Connected Dominating Sets

A dominating set \(D\) is connected if the induced subgraph:

$$
G[D]
$$

is connected.

Connected dominating sets are important in communication networks because domination alone does not guarantee communication between dominating vertices.

Applications include:

| Domain | Interpretation |
|---|---|
| Wireless routing | Backbone networks |
| Sensor systems | Communication infrastructure |
| Distributed systems | Coordination nodes |

## 65.14 Total Dominating Sets

A total dominating set requires every vertex, including those inside the set, to be adjacent to another dominating vertex.

Thus:

$$
\forall v \in V,
\quad
N(v)\cap D \ne \varnothing.
$$

Vertices may not dominate themselves.

This stronger requirement changes the theory substantially.

## 65.15 Roman Domination

Roman domination assigns labels:

| Label | Meaning |
|---|---|
| \(0\) | Unprotected |
| \(1\) | Light protection |
| \(2\) | Strong protection |

Every vertex labeled \(0\) must neighbor a vertex labeled \(2\).

The terminology comes from hypothetical Roman military defense strategies.

Roman domination has become an active research topic in domination theory.

## 65.16 Domatic Partitions

A domatic partition divides the vertex set into disjoint dominating sets.

The maximum number of dominating classes is called the domatic number.

Dense graphs tend to admit large domatic numbers.

Sparse graphs usually do not.

## 65.17 Domination in Random Graphs

Random graphs often have surprisingly small domination numbers.

In dense random graphs, a few vertices can dominate large portions of the graph.

Probabilistic methods estimate asymptotic domination behavior.

## 65.18 Domination and Network Design

Dominating sets naturally model control systems.

| Application | Dominating Interpretation |
|---|---|
| Cellular towers | Coverage stations |
| Sensor placement | Monitoring nodes |
| Social influence | Influential users |
| Emergency services | Facility placement |
| Communication networks | Backbone routers |

The goal is efficient coverage with minimal infrastructure.

## 65.19 Weighted Dominating Sets

Suppose vertices carry weights:

$$
w(v).
$$

The objective becomes minimizing:

$$
\sum_{v \in D} w(v).
$$

Weighted domination appears in:

| Area | Interpretation |
|---|---|
| Facility location | Construction costs |
| Sensor placement | Installation expense |
| Security systems | Resource allocation |

## 65.20 Domination and Graph Density

Sparse graphs often require larger dominating sets.

Dense graphs often admit small dominating sets.

### Example

| Graph | Domination Number |
|---|---|
| Complete graph | \(1\) |
| Sparse path | Approximately \(n/3\) |
| Star graph | \(1\) |

Domination therefore reflects global connectivity structure.

## 65.21 Upper and Lower Bounds

Several standard bounds hold.

### Degree Bound

If:

$$
\Delta(G)
$$

is the maximum degree, then:

$$
\gamma(G)
\ge
\frac{|V|}{\Delta(G)+1}.
$$

\gamma(G)\ge \frac{|V|}{\Delta(G)+1}

Indeed, one dominating vertex can cover at most:

$$
\Delta(G)+1
$$

vertices, including itself.

### Independence Bound

Every maximal independent set is dominating, so:

$$
\gamma(G)\le\alpha(G).
$$

## 65.22 Complexity

The minimum dominating set problem is NP-complete.

Moreover, it is difficult to approximate within small constant factors.

The problem remains computationally challenging even for many restricted graph families.

However, efficient algorithms exist for:

| Graph Class | Complexity |
|---|---|
| Trees | Polynomial |
| Interval graphs | Polynomial |
| Planar graphs | Better approximations |
| General graphs | NP-complete |

## 65.23 Common Relationships

| Parameters | Relation |
|---|---|
| Domination and independence | \(\gamma(G)\le\alpha(G)\) |
| Degree bound | \(\gamma(G)\ge |V|/(\Delta+1)\) |
| Maximal independent sets | Always dominating |

These relationships connect domination with sparsity and coverage.

## 65.24 Exercises

1. Compute \(\gamma(P_8)\).

2. Compute \(\gamma(C_9)\).

3. Prove that every maximal independent set is dominating.

4. Show that:

$$
\gamma(K_n)=1.
$$

5. Find a minimum dominating set of a star graph.

6. Prove:

$$
\gamma(G)\le\alpha(G).
$$

7. Explain why domination resembles set cover.

8. Give an example of a dominating set that is not independent.

9. Compute the domination number of a complete bipartite graph.

10. Explain why dense graphs tend to have small domination numbers.