Maximum number of objects in graph classes.

Abstract

The focus of this thesis is the study and implementation of two exact exponential time algorihms. These algorihms finds and lists the number of minimal dominating sets and the number of minimal subset feedback vertex sets in chordal and split graphs. Specifically the goal of this thesis is to study the upper and lower bounds on the number of minimal dominating sets and minimal subset feedback vertex sets in chordal and split graphs, to see whether it is possible to improve these bounds. In fact it will be shown that there exists a better lower bound on the number of minimal subset feedback vertex sets in split graphs.