Abstract

This thesis presents a new way to find the dominating set of a graph by introducing the concept of an orbit graph and a weighted dominating set. We showed that the Blokhuis-Lam method for the football pool problem is a special case of assuming that the solution has a non-trivial automorphism group. A general purpose algorithm for solving the dominating set problem is developed by using a coverage test, a wastage test, and the orbit and block structure of the graph's symmetry group to prune the search. The algorithm has been implemented and the program can be used to find all the dominating sets of any undirected, loopless, and labeled graph or all the weighted dominating sets of an orbit graph. The program analyzed grid graphs and football pool graphs, and was able to find the minimum dominating sets of any m x n grid graph for m X 10 and n X 11. For the football pool problem, we have determined that the automorphism group of n matches is S 3 [Special characters omitted.] S n and the automorphism group of a rook domain graph w n,q is S q [Special characters omitted.] S n . We also applied the orbit graph transformation to the football pool problem of 5, 6 and 7 matches. By considering only cyclic subgroups up to conjugacy, we generated 107 orbit graphs for the case of 5 matches, 220 orbit graphs for 6 matches and 428 orbit graphs for 7 matches. Using our program, we found dominating sets for 5 matches with size 27. For more matches, we found no better bounds within the limitations of our implementation. However, by using the mixed integer optimizer in the linear programming package CPLEX, we found weighted dominating sets, and hence, dominating sets matching the best known upper bounds. They also have more symmetry than the known solutions. There is hope that some of the unsolved orbit graphs can lead to smaller dominating sets.