The Inverse Domination Number Problem, DI-Pathological Graphs, and Fractional Analogues
Date
2010-04-20Type of Degree
dissertationDepartment
Mathematics and Statistics
Metadata
Show full item recordAbstract
The conjecture that $\alpha(G) \geq \gamma'(G)$ is unproven where $\alpha(G)$ is the vertex independence number and $\gamma'(G)$ is the inverse domination number of a simple graph G. We have found the conjecture to be true for all graphs with domination number less than 5 and for many other infinite classes of graphs. We examine related questions involving DI-pathological graphs which are graphs such that every maximal independent set intersects with every minimum dominating set. Finally, we use two central results in linear programming to characterize minimum fractional total dominating functions as well as maximum fractional open neighborhood packings for certain graphs.