The Inverse Domination Number Problem, DI-Pathological Graphs, and Fractional Analogues

Abstract

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.