
A dominating set S of a graph G is a subset of the vertex set of
G such that every vertex v of G is either in S or it has at least one
neighbour in S.
(a) [1 mark] How small can a minimum dominating set be for a connected graph on n vertices?
Give an example of a graph on 8 vertices that realizes your bound.
(b) [1 mark] How big can a minimum dominating set be for a graph on n vertices?
Give an example of a graph on 8 vertices that realizes your bound.
(c) [3 marks] How big can a minimum dominating set be for a connected graph on n vertices?
Give an example of a graph on 8 vertices that realizes your bound.
Given a connected nvertex graph G, your answer to (a) is giving a
lower bound
on the size of its minimum dominating set and (c) gives an
upper bound.

Consider the graph G:
(a) [1 mark] What is the degree sequence of G?
(b) [1 mark] List the degrees in order from smallest to largest.
(c) [2 marks] Give a tight lower bound B on the size of a minimum dominating
set for a graph with this degree sequence.
(d) [2 marks]
Draw a graph with the same multiset of degrees as G
that has a dominating set of size B (from part (c)).
(e) [2 marks] Give a minimum dominating set for G.
(f) [7 marks] Prove that G has no dominating sets of size B (from part (c)).
Hint: you probably have to do a case by case analysis for your
proof. For example, maybe start by considering two cases:
Case 1: Vertex 0 is in the dominating set.
Case 2: Vertex 0 is not in the dominating set.
The cases can have subcases that you should number systematically,
for example Cases 1.1 and 1.2.

A kprism is a 3regular graph on 2k vertices that has two kcycles,
and edges connecting the ith vertex on the first kcycle to the
ith vertex on the second kcycle.
Number the vertices of a kprism so that one cycle is
labelled with
with 0, 1, 2, ... , k1, and the other cycle
is labelled with k, k+1, ..., 2k1. The remaining
edges connect vertex i to vertex i+k for i = 0 to k1.
(a) [5 marks]
Find a minimum dominating set
for the kprism for k=3, 4, 5, 6
and show your answers on the
attached Prism Worksheet
(b) [5 marks] Give a formula for the minimum dominating set order
of a kprism in terms of the number of vertices that it has.
Hint: your formula should consider four cases:
n/2 is congruent to 0, 1, 2, or 3 modulo 4.
[Definition: For integers, n, r, and k, n is conguent to r modulo k
if n= ck + r for some integer c.]
(c) [10 marks] For each case from (b), argue that it is not possible to
find a smaller dominating set.
For questions #4 and #5, the algorithms presented operate
by assigning colors to the vertices of a graph.
Initially all vertices are white (undecided).
Red vertices are in the dominating set, and blue ones are excluded.
The dominating set D returned by the algorithm is
the set of red vertices.

[10 marks] One iteration of Algorithm #1 (Random Vertex Order Greedy)
behaves as follows.
A random permutation p of 0 to n1 is
generated.
Then for i from 0 to n1, vertex p[i]
is colored blue
as long as the resulting colored graph has no
blue vertices with all blue neighbours.
Otherwise, p[i] is colored red.
Given a graph G and a minimum dominating set D,
does there always exist some permutation p so that
Algorithm #1 returns D?
If you answer "yes", then explain how to compute such a permutation
p from the dominating set D.
If your answer is "no",
give a counterexample
consisting of a graph G and a minimum dominating set D,
and show that there is no permutation of the vertices
for which the algorithm returns D.

[10 marks] One iteration of Algorithm #2 (Random BFS order greedy)
A random root vertex r is selected.
BFS is performed on the graph starting with vertex r.
When the neighbours of a vertex are traversed, they are
traversed in random order.
The queue for the BFS contains a permutation p of the vertices
that we will call a BFSordering.
Algorithm #2 then proceeds as per Algorithm #1 using the
BFSordering p.
Given a graph G and a minimum dominating set D,
does there always exist some BFSordering p so that
Algorithm #1 returns D?
If you answer "yes", then explain how to compute such a
BFSordering p from the dominating set D.
If your answer is "no",
give a counterexample
consisting of a graph G and a minimum dominating set D,
and show that there is no BFSordering of the vertices
for which the algorithm returns D.