MSU-IIT campus

Domination
and its Variants

Jesica M. Anoche

August 18, 2026

Real-world situation
  • You’re the head of security in jail.
  • Every cell must be either guarded directly or watched by a neighboring guard.
  • You only have a minimum number of guards available.

How should you position the guards so that no cell is left unguarded?

C1
C4
C7
C2
C3
C5
C6
01 · Definitions

What is a Graph?

A graph G basically consists of

  • vertices – which are points / objects
  • edges – which are lines running between the vertices

Symbol:  G = (V(G), E(G))

  • V(G) – vertex set (contains all the vertices of G)
  • E(G) – edge set (contains all the edges of G)

card(V(G)) = |V(G)| = order of G
card(E(G)) = |E(G)| = size of G

Figure 1: a graph G with six vertices and nine edges
01 · Definitions

Adjacency & Neighbors

u is adjacent to v if u and v are connected by an edge.

uv

u is a neighbor of v  (or v is a neighbor of u).

Figure 1: a graph G with six vertices and nine edges
01 · Definitions

Dominating Set

Definition

A set D ⊆ V(G) is dominating if every vertex outside D is adjacent to at least one vertex in D.

γ(G) – minimum cardinality of a dominating set

Example: Consider the graph C5 and let D = {w1, w3}.

Cycle graph C5 with the dominating set highlighted
02 · Variants

Variants of Domination

Connected Dominating Set

– D is a dominating set + ⟨D⟩ is connected.

Connected Domination number

γc(G) – Minimum cardinality of a connected dominating set

C1
C4
C7
C2
C3
C5
C6
02 · Variants

Variants of Domination

Outer-Connected Dominating Set

– D is a dominating set + ⟨V(G)\D⟩ is connected.

Outer-Connected Domination number

γc˜(G) – Minimum cardinality of an outer-connected dominating set

C1
C4
C7
C2
C3
C5
C6
02 · Variants

Variants of Domination

Independent Dominating Set

– D is both dominating & Independent set

Independent Domination number

i(G) – Minimum cardinality of an independent dominating set

C1
C4
C7
C2
C3
C5
C6
03 · Applications

Social Network

03 · Applications

Other Applications

Domination

and its Variants

Emergency & Facility Location

Select minimum locations (stations, hospitals, fire centers) to cover all communities.

Communication & Wireless Networks

Choose a minimum set of nodes to maintain full coverage and connected communication.

Social Networks

Identify key individuals who can reach or influence the entire network.

Resource Distribution & Service Placement

Place service centers, schools, charging stations, or facilities strategically while avoiding unnecessary clustering.

Transportation & Road Networks

Ensure all intersections are accessible while keeping the remaining road network well-connected.

References

  1. S. A. Arriola and S. R. Canoy Jr., (1; 2)∗-Domination in Graphs, presented at The Asian Mathematical Conference (AMC), Bali, Indonesia, July 25–29 (2016).
  2. G. Mahalingam, Connected Domination in Graphs, M.A. thesis, Department of Mathematics, University of South Florida, 2005.
  3. M. H. Akhbari, R. Hasni, O. Favaron, H. Karami and S. M. Sheikholeslami, On the Outer-Connected Domination in Graphs, Journal of Combinatorial Optimization, 26(1), 10–18 (2013).
  4. W. Goddard, M. A. Henning, J. Lyle and J. Southey, On the Independent Domination Number of Regular Graphs, Annals of Combinatorics, 16(4), 719–732 (2012).

cityofiligan.com

Thank you

for listening and God bless.

1 / 15
← → to step · B to black the screen · ? for keys
1 / 12

← → step / reveal

Space next

B black screen

T timer

F fullscreen

Home / End first / last

? close this