Dominating Set

Question 1

In a graph G=(V,E), a _________ is a subset of vertices D⊆V such that every
vertex in the graph is either in D or
adjacent to a vertex in D.

Answer 1

dominating set

Question 2

y(G)

y(P_n)
y(K_n)
y(C_n)
y(K_{m,n}

Answer 2

domination number

n/3
1
n/3
2

Question 3

A dominating set where removing any
vertex means it stops being dominating.
-There can be many minimal dominating sets in a
graph.
- It is not necessarily the smallest possible set.

Answer 3

MINIMAL DOMINATING SET

Question 4

A dominating set with the smallest possible
number of vertices (the optimal one) among
all dominating sets.
- It’s always a minimal dominating set, but not all
minimal sets are minimum.
- There is usually one or few minimum sets, depending
on the graph.

Answer 4

MINIMUM DOMINATING SET

Question 5

The dominating set also forms a
connected subgraph.

Answer 5

CONNECTED DOMINATING SET

Question 6

Every vertex is adjacent to a vertex in
the set (even the ones inside the set
must be dominated by someone else in
the set).

Answer 6

TOTAL DOMINATING SET

Question 7

A dominating set where no two vertices
are adjacent (also an independent set).

Answer 7

INDEPENDENT DOMINATING SET