Instructions for all assignments:
Question | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
Marks | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
(a) [3] List all the automorphisms of this graph in
lexicographic order using one line notation.
(b) [4] Give the cycle structure notation for each of
the automorphisms from (a).
For the dominating sets for part (c) and (d)
show the relabelled dominating sets corresponding to
each automorphism and give the:
(c) [4] The dominating set is:
Click here for a worksheet for part (c).
(d) [4] The dominating set is:
Click here for a worksheet for part (d).
(b) [3] For each tree from (a), color the vertices of a minimum dominating set of the tree.
(c) [3] Make a conjecture (for n at least 2) for a formula for the maximum size of a minimum dominating set for a tree on n vertices and give examples to show that there are trees meeting this bound for each value of n at least 2.
(d) [6] Prove by induction that a tree has dominating set order at most the value given by your bound. Try using strong induction (you assume the formula is correct for n=2, 3, ..., n) in order to prove it is true for n+1. If you are using strong induction, you can remove more than one vertex from the tree at one step.
For questions 5-7 below, you can print as many copies as you need of these worksheets. Use the first two for doing clockwise-BFS in directions clockwise or counterclockwise. The unlabelled picture can be used for showing the non-equivalent labelled embeddings.
Be sure to indicate on each copy the number of the question you are answering.
(a) [3] Write down a permutation (in one line format) for each automorphism of the embedding.
How many automorphisms are there?
(b) [2] For this embedding and its automorphisms, what are the orbits for the vertices?
Two vertices u and v are in the same orbit
for this embedding if there is an automorphism
of the embedding that maps u to v.
(b) [4] Write down the resulting adjacency lists from (a).
(c) [3] Which of these adjacency lists is the lexicographic minimum?
(d) [4] Argue in terms of the embedding symmetries why it is that we do not have to consider other choices for r, f in order to ensure the lexicographic minimum has been found.
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 0 |
(a) [2] How many ways can you label the pictured embedding
(not worrying about symmetry-equivalence)
so that the adjacency matrix of the resulting
graph is the one given above for K_{3,3}.
Hint: make sure {0,1,2} is an independent set and
that {3,4,5} is an independent set.
Explain your reasoning for this question.
(b) [2] Compute the number of non-equivalent embeddings
of K_{3,3}
that look like the one pictured:
it will be your answer from (a) divided by the order of the
automorphism group for the embedding.
(c) [6] Show each of the different non-equivalent labellings
[that you counted in part (b)]
of the embedding of K_{3,3}.
0: 1 3 5 4 1: 0 4 6 2: 3 4 5 3: 0 6 4 2 4: 0 5 2 3 6 1 5: 0 6 2 4 6: 1 4 3 5
(a) [4] Use the face walking algorithm described in class to walk all the faces of this embedding.
(b) [2] What is the genus of the embedding and what surface does this correspond to?
(c) [4] Draw a nice picture of this embedding.
0: 1 3 5 1: 0 4 2 2: 1 3 5 3: 0 4 2 4: 1 3 5 5: 0 4 2
(a) [3] Use the face walking algorithm described in class to walk all the faces of this embedding.
(b) [1] What is the genus of the embedding and what surface does this correspond to?
(c) [2] Draw a nice picture of this embedding.
(d) [2] Is this graph isomorphic to the graph from question 5? If the answer is yes, provide an isomorphism. If the answer is no, justify your answer.
(e) [2] Is this embedding isomorphic to the embedding from question 5? If the answer is yes, provide an isomorphism. If the answer is no, justify your answer.