Independent Dominating Sets in Unicyclic Graphs

Wilf found the maximum number of independent dominating sets of a tree using algebraic methods, while Sagan gave an elementary proof. In this thesis, we maximize the number of independent dominating sets of unicyclic graphs, giving a new proof of a result of Jou and Chang. In our proof, we are able to reduce the problem to finding independent dominating sets of single-legged caterpillar graphs. We also study the number of single-legged caterpillar graphs, both oriented and unoriented, which are related to the Fibonacci Sequence. Finally, this thesis also examines the domination ratio in unicyclic graphs. The domination ratio is the quotient of the minimum size of an independent dominating set and the minimum size of a dominating set. Using a generalization of a technique of Furuya et al., we find a new bound on this ratio for unicyclic graphs