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)

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)

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
Maximal independent sets	Always dominating

These relationships connect domination with sparsity and coverage.

65.24 Exercises

Compute $\gamma(P_8)$ .
Compute $\gamma(C_9)$ .
Prove that every maximal independent set is dominating.
Show that:

\gamma(K_n)=1.

Find a minimum dominating set of a star graph.
Prove:

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

Explain why domination resembles set cover.
Give an example of a dominating set that is not independent.
Compute the domination number of a complete bipartite graph.
Explain why dense graphs tend to have small domination numbers.